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

Question

I have asked the question at Math SE and at SO, 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. 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.

Answer 1

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.

Answer 2

I'm going to develop the idea that Jukka Suomela 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.