📂Graph Theory

Geometric Dual Graphs

Definitions ¹

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.

■