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 polyhedral formula, for the vertices, edges a$n$d faces of a (co$n$vex) 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

2

(Edited as per Ilmari's comment.)

An edge does not lie on a cycle if and only if its removal increases the number of components of the graph.

  • 0
    @Graviton For an algorithm, you could try something like this: Remove the edge $xy$ from your graph. Starting with x, build any spanning tree of its component. If the spanning tree is built and does not contain the vertex $y$, then it must be that $y$ is not in the same component of $x$ after the removal of the edge $xy$. Thus, you would conclude that $xy$ did not lie on any internal face of the original graph. If the spanning tree does contain $y$, then the edge $xy$ lies on some internal face of the original graph.2011-08-28