# For a Planar Graph, Find the Algorithm that Constructs A Cycle Basis, with each Edge Shared by At Most 2 Cycles

In a planar graph $G$, one can easily find all the cycle basis by first finding the spanning tree ( any spanning tree would do), and then use the remaining edge to complete cycles. Given Vertex $V$, edge $E$, there are $C=E-V+1$ number of cycles, and there are $C$ number of edges that are inside the graph, but not inside the spanning tree.

Now, there always exists a set of cycle basis such that each and every edge inside the $G$ is shared by at most 2 cycles. My question is, is there any algorithm that allows me to find such a set of cycle basis? The above procedure I outlined only guarantees to find a set of cycle basis, but doesn't guarantee that all the edges in the cycle basis is shared by at most two cycles.

Note: Coordinates for each vertex are not known, even though we do know that the graph must be planar.

-
Find a planar embedding (there should be plenty of algorithms) and use the faces. This is in effect the same as the other answer. You could also try constructing the dual of the graph directly, if faster algorithms for that exist. –  Aryabhata Nov 30 '10 at 17:22
@Moron It seems strange to use acual embeddings for something so algebraic-looking. Maybe there is a more direct algorythm? Also, what is an algorythm for embedding? Are the faces easy to determine from it? –  Max Nov 30 '10 at 18:54
@Max: Finding planar embeddings of a planar graph is a well known problem. Google should find plenty for you. Yes, the faces should be easy to determine once we have the embedding. I agree, maybe there is a better algorithm, and that is the reason I left a comment, instead of an answer. –  Aryabhata Nov 30 '10 at 19:14
@Moron, is it possible to provide a link? I did a google search on the terms you suggested ( planar embedding faces) but I don't think they are helpful at all –  Graviton Dec 1 '10 at 3:34
@Ngu: Don't add faces to the search. Just do planar embedding. –  Aryabhata Dec 1 '10 at 6:25

To suppliment Aryabhata's comment: yes, using plane embedding algorithm will do. One of such algorithm is Boyer and Myrvold.

-

I agree with all the commenters who say that you should just find a planar embedding. However, I happened to stumble across a description that might make you happy:

Let $G$ be a three-connected planar graph and let $C$ be a cycle. Let $G/C$ be the graph formed by contracting $C$ down to a point. Then $C$ is a face of the planar graph if and only if $G/C$ is two-connected.

In particular, this lemma is useful in proving that a three-connected graph can only be planar in one way, a result of Whitney.

But testing this for every cycle is much less efficient than just finding the planar embedding.

-