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?

  • $\begingroup$ 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. $\endgroup$ – Austin Mohr Aug 27 '11 at 6:01
  • $\begingroup$ @Austin, I've updated the terminology $\endgroup$ – Graviton Aug 27 '11 at 6:22
  • $\begingroup$ 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. $\endgroup$ – Gerry Myerson Aug 27 '11 at 6:34
  • $\begingroup$ The graph is being given as a list of edge. $\endgroup$ – Graviton Aug 27 '11 at 6:55
  • $\begingroup$ 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. $\endgroup$ – Joseph Malkevitch Aug 27 '11 at 13:05

(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.

  • $\begingroup$ Austin, can you elaborate more on this? $\endgroup$ – Graviton Aug 27 '11 at 6:19
  • $\begingroup$ I thought of this, but I don't think this is true. For one, my graph can contain 2 disconnected trees. So it doesn't make sense to say that its removal disconnects the graph. $\endgroup$ – Graviton Aug 27 '11 at 7:44
  • 2
    $\begingroup$ @Graviton: If you interpret "disconnects the graph" as "increases the number of connected components" (or as "disconnects the component it belongs to"), then it should still be true. $\endgroup$ – Ilmari Karonen Aug 27 '11 at 8:46
  • $\begingroup$ @Ilmari, even if I can make branch-edge and face-edge into two different components, how can I tell which component is branch-edge type, and which is face-edge type? $\endgroup$ – Graviton Aug 27 '11 at 8:55
  • $\begingroup$ @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. $\endgroup$ – Austin Mohr Aug 28 '11 at 19:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.