<p>I'm going to develop the idea that Jukka Suomela suggests in the comments. $\newcommand{\lk}{\operatorname{lk}}$  </p>

<p>We are given a connected graph $G = (V, E)$ and a $Z/2Z$-cycle basis $F$.  Note that $|F| = |E| - |V| + 1$.  For each cycle $f \in F$ glue a disk $D_f$ along $f$ to $G$.  The resulting $2$-complex $K$ has Euler characteristic $\chi(K) = |V| - |E| + |F| = 1$.</p>

<p>Definition: A <em>cactus</em> is a tree-like union of edges and disks. (For example, if $D$ and $D&#39;$ are disks and $v, v&#39;$ are points of $D,D&#39;$ then gluing $v$ to $v&#39;$ is a cactus.)</p>

<blockquote>
  <p>Theorem: If every edge $e \in E$ meets at most two cycles in $F$ then $K$ is a cactus.  </p>
</blockquote>

<p>Thus finding such a cycle basis "easily" gives a planar embedding.</p>

<p>Definition: The <em>vertex link</em> $\lk(v)$ of $v \in V$ is the union of arcs coming from the "corners" of the disks $D_f$ that are adjacent to $v$.  (We also need to throw in points for each end of each edge adjacent to $v$.)  So, for example, if $K$ is a closed surface without boundary then all links are circles.  If $K$ is a connected surface then all links are circles or intervals. (Here, $\lk(v)$ is an interval iff $v$ is a boundary point of $K$.)  If $K$ is a cone $x^2 + y^2 = z^2$ in $R^3$ then the link of the origin is the disjoint union of two circles. </p>

<p>Claim: The inclusion map $\lk(v) \to K - v$ is one-to-one in terms of connected components.  (Ie, an isomorphism of $\pi_0$.)</p>

<p>Proof: Suppose that $A, B$ components of $\lk(v)$ lie in the same component $X \subset K - v$. Choose an edge cycle $P$ in $X \cup v$ that meets $v$ exactly once, exits $v$ through $A$ and enters $v$ through $B$. Since $F$ is a $Z/2Z$-cycle basis $P$ is null-homologous in $K$ (working with $Z/2Z$ coefficients!) Thus there is a (possibly non-oriented) surface $S$ embedded in $K$ with $\partial S = P$.  Thus $A$ and $B$ lie in the same connected component of $\lk(v)$ and so $A = B$, proving the claim.</p>

<p>In particular, if $\lk(v)$ is disconnected then $v$ is a cut vertex.  Also, elements of $F$ meet at most one component of $\lk(v)$. </p>

<p>Proof of the theorem: We induct on the number of vertices $v$ so that $\lk(v)$ is not connected.  </p>

<p>Base case: if there are no such vertices then every link is either a point, an interval, or a circle.  If any link is a point then $G$ is an edge, $F$ is empty, and we are done.  So we may assume that $K$ is a surface.  Since $\chi(K) = 1$ the surface $K$ is either homeomorphic to the disk $D^2$ or to the real projective plane $RP^2$.  However, $RP^2$ has nontrivial $H_1$ with $Z/2Z$ coefficients, contradicting our assumption that $F$ was a basis.  </p>

<p>Induction step: Suppose that $v$ has disconnected link.  Then let $K_i$ be the components of $K - v$.  Add a vertex $v_i$ to each of these to get a disjoint collection of $2$-complexes.  By the Claim, the cycle basis for the one-skeleton $K^{(1)}$ (ie for $G$) is a disjoint union of bases for the $K^{(1)}_i$ and the theorem is proved.</p>

CC BY-SA 3.0
2013-03-24T18:30:48.957Z
It is a theorem of Saunders Mac Lane (A combinatorial condition for planar graphs, 1937) that a graph G is planar if and only if G has a cyclic basis (mod 2) that mentions every edge at most once.
Sam Nead
CC BY-SA 3.0
2013-03-24T18:37:59.783Z
Mac Lane's paper "A structural characterization of planar combinatorial graphs", from the same year, also looks relevant, but I can only read the first page.
Sam Nead
CC BY-SA 2.5
2010-12-04T03:04:16.563Z
2010-12-04T03:22:12.077Z
2010-12-04T03:22:12.077Z
Sam Nead
<p>Construct a planar embedding and use all but one of the faces of the embedding as cycles in the cycle basis. (It doesn't matter which one you leave out.)</p>

<p>Note that there are actually two different subproblems in planar embedding: determining the cyclic ordering of the edges around each vertex, and computing explicit coordinates. But for the cycle basis, you only need the cyclic ordering, since that's what determines the structure of the faces; you don't need any kind of "nice" coordinates.</p>

<p>Finding planar embeddings is linear time but complicated; there are several standard algorithms.</p>

CC BY-SA 2.5
2010-12-02T01:10:50.770Z
@David, are you saying that I can construct planar embedding and read off the polygonal faces without assigning the coordinates to vertex? Do you have a paper ( or even better, code!!) for these kinds of algorithm?
Graviton
CC BY-SA 2.5
2010-12-02T01:14:51.420Z
Yes, just walk from edge to edge around each face using the cyclic ordering to tell you which edge to walk to at each step.
David Eppstein
CC BY-SA 2.5
2010-12-02T01:18:03.897Z
@David, not to sure what you mean here. I think my goal is to determine the face. So the face is not known beforehand. How can I *walk from edge to edge around each face* ?
Graviton
CC BY-SA 2.5
2010-12-02T01:47:53.170Z
From oriented edge uv, look in the cyclic order at v to find the next edge vw. Then look in the cyclic order at w to find the next edge wx, etc. When you get back to uv, you've found one face. Do it for all orientations of all edges, and you find all faces.
David Eppstein
CC BY-SA 2.5
2010-12-02T01:57:29.460Z
@David, I see. But I afraid that this algorithm won't guarantee that any edge is shared by at most two faces? And what if at *w* there are more than 2 edges connected to it? which edge to choose then?
Graviton
CC BY-SA 2.5
2010-12-02T02:15:54.520Z
The hard part is hidden in the phrase "Finding planar embeddings is linear time but complicated; there are several standard algorithms." You need to use one of these complicated algorithms.
Peter Shor 
CC BY-SA 2.5
2010-12-02T02:17:43.673Z
Each edge is in at most two faces, the ones found by walking in this way from its two orientations. (If it is a bridge, both orientations are part of a single face.) Actually this part is true for any cyclic orientation of edges around each vertex of any graph. The part that requires planarity to prove is the fact that the faces form a cycle basis.
David Eppstein
CC BY-SA 2.5
2010-12-02T02:35:09.630Z
@Peter and David, by planar embedding algorithm I assume that you mean algorithm such as [Boyer and Myrvold](http://jgaa.info/accepted/2004/BoyerMyrvold2004.8.3.pdf)?
Graviton
CC BY-SA 2.5
2010-12-02T04:48:27.880Z
Yes. I would have also suggested Brandes' preprint "the left-right planarity test", another simplified variant of a planarity testing, but unfortunately he seems to have locked it.
David Eppstein
CC BY-SA 2.5
2010-12-02T08:51:31.797Z
By the way, can we show that finding a cycle basis like this is at least as difficult as finding a planar embedding? Given the cycle basis, can we easily construct a planar embedding?
Jukka Suomela
CC BY-SA 2.5
2010-12-04T03:37:42.037Z
@ Jukka - I think (think!) that I've answered your question in the affirmative.  I've posted it as an answer to OP's question.
Sam Nead
CC BY-SA 2.5
2010-12-02T01:00:04.510Z
2010-12-02T01:11:35.167Z
2010-12-02T01:11:35.167Z
David Eppstein
<p>I have asked the question at <a href="https://math.stackexchange.com/questions/12488/for-a-planar-graph-find-the-algorithm-that-constructs-a-cycle-basis-with-each-e">Math SE</a> and at <a href="https://stackoverflow.com/questions/4315545/algorithm-to-construct-cycle-basis-with-the-condition-that-each-edge-must-be-sha">SO</a>, but I can't seem to get the answer I want. So I paraphrase the question and it here.</p>

<p>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 edges to complete cycles. Given Vertex $V$, edge $E$, there are $C=E−V+1$ number of cycles ( Euler formula), and there are $C$ number of edges that are inside the graph, but not inside the spanning tree.</p>

<p>Now, <a href="https://math.stackexchange.com/questions/12465/for-a-planar-graph-is-it-always-possible-to-construct-a-set-of-cycle-basis-with">there always exists a set of cycle basis such that each and every edge inside the $G$ is shared by at most 2 cycles</a>. 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.</p>

<p>One of the suggestion I got from Math SE is to use planar embedding algorithm to "guess" the most natural coordinates for each vertex ( so that the graph looks "nice" visually), and then construct the polygonal faces. But this is exceptionally long-winded. I believe that this problem can be tackled more simply without involving coordinates. </p>

<ds.algorithms><graph-theory><graph-algorithms>
For a Planar Graph, Find the Algorithm that Constructs A Cycle Basis, with each Edge Shared by At Most 2 Cycles
Graviton
# For a Planar Graph, Find the Algorithm that Constructs A Cycle Basis, with each Edge Shared by At Most 2 Cycles

(Asked by: username_0 on 2010-12-02)

I have asked the question at [Math SE](https://math.stackexchange.com/questions/12488/for-a-planar-graph-find-the-algorithm-that-constructs-a-cycle-basis-with-each-e) and at [SO](https://stackoverflow.com/questions/4315545/algorithm-to-construct-cycle-basis-with-the-condition-that-each-edge-must-be-sha), but I can't seem to get the answer I want. So I paraphrase the question and it here.

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 edges to complete cycles. Given Vertex $V$, edge $E$, there are $C=E−V+1$ number of cycles ( Euler formula), 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](https://math.stackexchange.com/questions/12465/for-a-planar-graph-is-it-always-possible-to-construct-a-set-of-cycle-basis-with). 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.

One of the suggestion I got from Math SE is to use planar embedding algorithm to "guess" the most natural coordinates for each vertex ( so that the graph looks "nice" visually), and then construct the polygonal faces. But this is exceptionally long-winded. I believe that this problem can be tackled more simply without involving coordinates.

**Tags:** ds.algorithms, graph-theory, graph-algorithms


---

## 2 answers

### Answer by username_2 on 2010-12-02. Score: 13 | Accepted answer

Construct a planar embedding and use all but one of the faces of the embedding as cycles in the cycle basis. (It doesn't matter which one you leave out.)

Note that there are actually two different subproblems in planar embedding: determining the cyclic ordering of the edges around each vertex, and computing explicit coordinates. But for the cycle basis, you only need the cyclic ordering, since that's what determines the structure of the faces; you don't need any kind of "nice" coordinates.

Finding planar embeddings is linear time but complicated; there are several standard algorithms.

> **Comments:**
> **username_0**: @David, are you saying that I can construct planar embedding and read off the polygonal faces without assigning the coordinates to vertex? Do you have a paper ( or even better, code!!) for these kinds of algorithm?  
> **username_2**: Yes, just walk from edge to edge around each face using the cyclic ordering to tell you which edge to walk to at each step.  
> **username_0**: @David, not to sure what you mean here. I think my goal is to determine the face. So the face is not known beforehand. How can I *walk from edge to edge around each face* ?  
> **username_2**: From oriented edge uv, look in the cyclic order at v to find the next edge vw. Then look in the cyclic order at w to find the next edge wx, etc. When you get back to uv, you've found one face. Do it for all orientations of all edges, and you find all faces.  
> **username_0**: @David, I see. But I afraid that this algorithm won't guarantee that any edge is shared by at most two faces? And what if at *w* there are more than 2 edges connected to it? which edge to choose then?  
> **username_3**: The hard part is hidden in the phrase "Finding planar embeddings is linear time but complicated; there are several standard algorithms." You need to use one of these complicated algorithms.  
> **username_2**: Each edge is in at most two faces, the ones found by walking in this way from its two orientations. (If it is a bridge, both orientations are part of a single face.) Actually this part is true for any cyclic orientation of edges around each vertex of any graph. The part that requires planarity to prove is the fact that the faces form a cycle basis.  
> **username_0**: @Peter and David, by planar embedding algorithm I assume that you mean algorithm such as [Boyer and Myrvold](http://jgaa.info/accepted/2004/BoyerMyrvold2004.8.3.pdf)?  
> **username_2**: Yes. I would have also suggested Brandes' preprint "the left-right planarity test", another simplified variant of a planarity testing, but unfortunately he seems to have locked it.  
> **username_4**: By the way, can we show that finding a cycle basis like this is at least as difficult as finding a planar embedding? Given the cycle basis, can we easily construct a planar embedding?  
> **username_1**: @ Jukka - I think (think!) that I've answered your question in the affirmative.  I've posted it as an answer to OP's question.  

---

### Answer by username_1 on 2010-12-04. Score: 6

I'm going to develop the idea that username_4 suggests in the comments. $\newcommand{\lk}{\operatorname{lk}}$

We are given a connected graph $G = (V, E)$ and a $Z/2Z$-cycle basis $F$. Note that $|F| = |E| - |V| + 1$. For each cycle $f \in F$ glue a disk $D\_f$ along $f$ to $G$. The resulting $2$-complex $K$ has Euler characteristic $\chi(K) = |V| - |E| + |F| = 1$.

Definition: A *cactus* is a tree-like union of edges and disks. (For example, if $D$ and $D'$ are disks and $v, v'$ are points of $D,D'$ then gluing $v$ to $v'$ is a cactus.)

> Theorem: If every edge $e \in E$ meets at most two cycles in $F$ then $K$ is a cactus.

Thus finding such a cycle basis "easily" gives a planar embedding.

Definition: The *vertex link* $\lk(v)$ of $v \in V$ is the union of arcs coming from the "corners" of the disks $D\_f$ that are adjacent to $v$. (We also need to throw in points for each end of each edge adjacent to $v$.) So, for example, if $K$ is a closed surface without boundary then all links are circles. If $K$ is a connected surface then all links are circles or intervals. (Here, $\lk(v)$ is an interval iff $v$ is a boundary point of $K$.) If $K$ is a cone $x^2 + y^2 = z^2$ in $R^3$ then the link of the origin is the disjoint union of two circles.

Claim: The inclusion map $\lk(v) \to K - v$ is one-to-one in terms of connected components. (Ie, an isomorphism of $\pi\_0$.)

Proof: Suppose that $A, B$ components of $\lk(v)$ lie in the same component $X \subset K - v$. Choose an edge cycle $P$ in $X \cup v$ that meets $v$ exactly once, exits $v$ through $A$ and enters $v$ through $B$. Since $F$ is a $Z/2Z$-cycle basis $P$ is null-homologous in $K$ (working with $Z/2Z$ coefficients!) Thus there is a (possibly non-oriented) surface $S$ embedded in $K$ with $\partial S = P$. Thus $A$ and $B$ lie in the same connected component of $\lk(v)$ and so $A = B$, proving the claim.

In particular, if $\lk(v)$ is disconnected then $v$ is a cut vertex. Also, elements of $F$ meet at most one component of $\lk(v)$.

Proof of the theorem: We induct on the number of vertices $v$ so that $\lk(v)$ is not connected.

Base case: if there are no such vertices then every link is either a point, an interval, or a circle. If any link is a point then $G$ is an edge, $F$ is empty, and we are done. So we may assume that $K$ is a surface. Since $\chi(K) = 1$ the surface $K$ is either homeomorphic to the disk $D^2$ or to the real projective plane $RP^2$. However, $RP^2$ has nontrivial $H\_1$ with $Z/2Z$ coefficients, contradicting our assumption that $F$ was a basis.

Induction step: Suppose that $v$ has disconnected link. Then let $K\_i$ be the components of $K - v$. Add a vertex $v\_i$ to each of these to get a disjoint collection of $2$-complexes. By the Claim, the cycle basis for the one-skeleton $K^{(1)}$ (ie for $G$) is a disjoint union of bases for the $K^{(1)}\_i$ and the theorem is proved.

> **Comments:**
> **username_1**: It is a theorem of Saunders Mac Lane (A combinatorial condition for planar graphs, 1937) that a graph G is planar if and only if G has a cyclic basis (mod 2) that mentions every edge at most once.  
> **username_1**: Mac Lane's paper "A structural characterization of planar combinatorial graphs", from the same year, also looks relevant, but I can only read the first page.  

---

