0
$\begingroup$

I have a planar graph $G$ consisting of the edges and vertices $(E,V)$. And so, there are $C=E-V+1$ faces in total. The graph is given as a list of edges.

The question is, how to find the edges that don't lie on the faces of the graph? One way I can think of is to find the spanning tree of the graph, use the non-spanning-tree edges to complete the faces, and get all the edges on the faces. Since we already have the on-face edges, we can obtain the not-on-face edges by subtracting the on-face edges from the all the edges.

But is there a more direct way of doing this?

  • 0
    Euler's formula is about the number of faces of a graph, not the number of cycles. For example, $K_4$ minus an edge has two faces, but three cycles.2011-08-27
  • 0
    @Austin, I've updated the terminology2011-08-27
  • 0
    I *think* you're asking for the edges that don't lie on any faces at all. So why not just look at the graph and pick out those edges? Of course, that won't work if the graph isn't given to you as a drawing on paper, but you haven't said how the graph is given to you, and there is no good way to answer your question if we don't know how the graph is represented.2011-08-27
  • 0
    The graph is being given as a list of edge.2011-08-27
  • 0
    Euler's polyhedral formula, for the vertices, edges and faces of a (convex) polyhedron states: V + F - E = 2. The graph theory version of this is that V + F - E = 2 for a connected graph embedded in the plane (edges meet only at vertices - plane graphs). For a tree, a connected graph with no circuits, there is one face, the "infinite" or unbounded face. If the graph is not connected you have to modify the formula above to deal with the number of components of the graph.2011-08-27

1 Answers 1