Graph Duality

Graph Duality

Definition: For a planar graph $G$, the dual of $G$ denoted $G^*$ is a graph obtained by replacing all faces in $G$ with vertices, and connecting vertices with edges if those faces share an edge.

For example, let's look at the following graph $G$ and a dual of $G$, $G^*$:

Screen%20Shot%202014-04-08%20at%201.57.03%20PM.png

Note that just because two graphs $G$ and $H$ are isomorphic ( $G \cong H$ ), these duals are not necessarily isomorphic. Hence $G \cong H \nRightarrow G^* \cong H^*$

We will now look at some properties of graph duals.

Lemma 1: Suppose that $G$ is a planar graph with $v$ vertices, $e$ edges, and $f$ faces. The dual, of $G$, $G^*$ hence has $f$ vertices, $e$ edges, and $v$ faces.
  • **Proof: In the construction of $G^*$, we know that the dual of $G$ must have precisely $f$ vertices and $e$ edges by definition. We can now apply Euler's formula to get that for the graph $G$ we have $v - e + f = 2$, and that for the dual we get that:
(1)
\begin{equation} f - e + f^* = 2 \end{equation}
  • We note that the only difference between these two equations is $f^*$ and n. Hence $f^* = n$. $\blacksquare$

Correspondences of Duals

We will now summarize a list of properties relating planar graphs and their duals.

Planar Graph $G$ Correspondence in $G^*$
An edge in $G$ An edge in $G^*$
A face in $G$ A vertex in $G^*$
A vertex in $G$ A face in $G^*$
A cycle of length $k$ in $G$ A cutset in $G^*$ with $k$ edges
A cutset of $G$ with $k$ edges A cycle of length $k$ in $G^*$

Duals of a Dual

Suppose that we have a graph G and find a dual $G^*$. If we then take a dual of $G^*$, then what do we get? It turns out that $G^{**} = G$. This should make sense as essentially we are interchanging planar faces and vertices once again.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License