The cycle space of a planar graph is the cut space of its dual graph

807 Views Asked by At

I am trying to understand the following statement on wikipedia:

The cycle space of a planar graph is the cut space of its dual graph, and vice versa.

Suppose we have a cycle space $\mathcal C(G)$. By this statement we have $\mathcal C(G)=\mathcal C^*(G^*)$ where $G^*$ is the dual of $G$ and $C^*(H)$ denotes the cut space of a graph $H$.

This statement makes no sense to me if the dual referred to is the geometric dual since the constituent edge sets in the two subspaces are entirely different. One option to make sense of this statement is to understand the dual as an abstract dual in the sense described by the following:

The edges of $G$ and its dual are the same and the cut-sets of $G$ are the cycles of its dual and vice versa.

This is how I find it described in my book. My question is is there a way to make sense of this statement for the geometric dual?

1

There are 1 best solutions below

0
On BEST ANSWER

It's true that the edge sets are different, but for each edge in the geometric dual, there's a corresponding edge in the original graph: if an original-graph edge $e$ lies between regions $A$ and $B$ with "centers" $a$ and $b$, then there's a dual-graph edge $e'$ from $a$ to $b$ that "crosses" the edge $e$. (If you insert a vertex in the middle of $e$, splitting it into two edges, then you get two edges in the dual graph from $a$ to $b$, one corresponding to each sub-edge). So while the two edge sets are different, this natural pairing makes for a pretty nice correspondence.