Geometric Dual Graphs
Definitions 1
For a given planar graph $G$, the geometric dual graph $G^{ \ast }$ is constructed as follows:
- Step 1.
Place a vertex $v^{ \ast }$ corresponding to each face $f$ of $G$. - Step 2.
Draw an edge $e^{ \ast }$ corresponding to each edge $e$ of $G$, such that it overlaps. - Step 3.
Erase the original graph and use the vertices $v^{ \ast }$ and edges $e^{ \ast }$ to form the graph $G^{ \ast }$.
- The regions distinguished on the plane by drawing a planar graph are called faces.
Description
Duality is a universal concept commonly found throughout mathematics and physics, appearing in functional analysis as dual spaces, for example. Specifically, let’s create the dual graph $G^{ \ast }$ for the following graph $G$:
Graph $G$ has three faces $f_{1} , f_{2}, f_{3}$. Place three vertices $v^{ \ast }$ corresponding to each face as follows.
Now, draw edges $e^{ \ast }$ connecting each $v^{ \ast }$. However, these edges must all pass through the original graph’s edges $G$.
If we erase the original graph, only the desired dual graph $G^{ \ast }$ of $G$ remains. Note that there’s no reason why $G^{ \ast }$ should be a simple graph just because $G$ is.
Meanwhile, the dual graph possesses the following intuitive properties, particularly property [3], which suggests the possibility for the concept of duality to be abstractly extended.
Basic Properties
- [1]: If a connected planar graph $G$ has $n$ vertices, $m$ edges, and $f$ faces, and its geometric dual graph $G^{ \ast }$ has $n^{ \ast }$ vertices, $m^{ \ast }$ edges, and $f^{ \ast }$ faces, $$ n^{ \ast } = f \\ m^{ \ast } = m \\ f^{ \ast } = n $$
- [2]: If $G$ is a connected planar graph, then $G^{\ast \ast}$ is isomorphic to $G$.
- [3]: For a planar graph $G$ and its geometric dual graph $G^{ \ast }$, $C \subset E(G)$ being a cycle $\iff$ $C^{ \ast } \subset E \left( G^{ \ast } \right)$ becomes a cutset
Proof
[3]
$(\Rightarrow)$
A cycle $C$ in $G$ will necessarily encompass at least one face, so there exists a set of vertices $S \ne \emptyset$ in $G^{ \ast }$ corresponding to these faces. Removing $C^{ \ast }$ corresponding to $C$ in $G^{ \ast }$ divides it into two subgraphs consisting solely of $S$ and $V(G) \setminus S$, making $C^{ \ast }$ a cutset of $G^{ \ast }$.
$(\Leftarrow)$
As this is essentially the same, it is omitted.
■
Wilson. (1970). Introduction to Graph Theory: p73. ↩︎