Chapter 42. Dual Graphs

Duality is one of the central constructions in planar graph theory. It turns the faces of a plane graph into vertices and turns the edges separating faces into edges of a new graph. The result is called the dual graph.

The construction depends on a fixed plane embedding. For this reason, the dual graph belongs naturally to plane graphs, not merely to abstract planar graphs. The same planar graph may have different embeddings, and different embeddings may produce different dual graphs.

42.1 Definition

Let $G$ be a connected plane graph. The dual graph of $G$ , denoted by

G^\ast,

is constructed as follows.

Place one vertex of $G^\ast$ in each face of $G$ . For every edge $e$ of $G$ , draw one edge $e^\ast$ crossing $e$ . This dual edge joins the two dual vertices corresponding to the faces on the two sides of $e$ .

Thus

V(G^\ast) = \{\text{faces of }G\},

and

E(G^\ast) = \{e^\ast : e \in E(G)\}.

There is exactly one dual edge for each primal edge. Therefore

|E(G^\ast)| = |E(G)|.

The vertices of the dual graph correspond to faces of the original graph. The edges of the dual graph correspond to edges of the original graph.

42.2 The Primal and the Dual

The original plane graph is often called the primal graph. Its dual is the graph built from its faces.

Primal graph $G$	Dual graph $G^\ast$
Vertex	Face-related structure
Edge	Dual edge
Face	Vertex
Face adjacency	Vertex adjacency
Cycle	Cut-like structure

The correspondence between faces and vertices is the most visible part of duality. The deeper part is the correspondence between cycles and cuts, which will be studied later in the chapter.

42.3 Example: A Cycle

Consider the cycle graph $C_n$ . Its plane embedding has two faces: the inside face and the outer face.

Thus the dual graph has two vertices. Each edge of the cycle separates the inside face from the outer face, so each primal edge gives a dual edge between the same two dual vertices.

Therefore the dual of $C_n$ is a multigraph with two vertices joined by $n$ parallel edges.

For example, the dual of $C_4$ has two vertices and four parallel edges.

This example shows why dual graphs are often allowed to be multigraphs. Even when $G$ is simple, $G^\ast$ may have multiple edges.

42.4 Example: A Tree

Let $T$ be a tree. A plane embedding of a tree has only one face, the outer face. Therefore $T^\ast$ has one vertex.

Each edge of $T$ has the outer face on both sides. Hence each edge of $T$ becomes a loop in the dual graph.

If $T$ has $e$ edges, then $T^\ast$ consists of one vertex with $e$ loops.

This example shows that loops naturally occur in dual graphs. Even when the original graph has no loops, the dual may contain loops.

42.5 Loops and Bridges

Duality exchanges loops and bridges.

A bridge in $G$ is an edge whose deletion increases the number of connected components. In a plane embedding, a bridge has the same face on both sides. Therefore its dual edge is a loop in $G^\ast$ .

Conversely, if $G$ has a loop, that loop encloses a face and separates it from another face. The corresponding dual edge is a bridge.

Thus:

In $G$	In $G^\ast$
Bridge	Loop
Loop	Bridge
Ordinary edge between two faces	Ordinary dual edge

This is one of the first signs that duality reverses certain graph-theoretic roles.

42.6 Duals May Have Multiple Edges

A dual graph may have parallel edges. This occurs when two faces of $G$ share more than one edge.

For example, in a cycle $C_n$ , the inside and outside faces share every edge of the cycle. The dual therefore has $n$ parallel edges between two dual vertices.

For this reason, the category of plane graphs used in duality usually allows loops and multiple edges. Restricting only to simple graphs would make the dual construction unstable.

42.7 The Outer Face

The outer face receives a dual vertex just like every other face. There is no exception in the construction.

If a primal edge lies on the boundary of the outer face and also on the boundary of a bounded face, then its dual edge joins the dual vertex of the outer face to the dual vertex of that bounded face.

This convention is essential. Without the outer face, the dual graph would lose information, Euler’s formula would fail in dual form, and the dual edge count would no longer match the primal edge count.

42.8 Counting in the Dual

Let $G$ be a connected plane graph with

v = |V(G)|,\qquad e = |E(G)|,\qquad f = |F(G)|.

Then the dual graph satisfies

|V(G^\ast)| = f,

|E(G^\ast)| = e.

If $G^\ast$ is connected, then its faces correspond to the vertices of $G$ , so

|F(G^\ast)| = v.

Thus duality interchanges vertices and faces while keeping edges fixed.

Quantity	In $G$	In $G^\ast$
Vertices	$v$	$f$
Edges	$e$	$e$
Faces	$f$	$v$

Euler’s formula is self-dual:

v - e + f = 2

becomes

f - e + v = 2.

The same equation remains true after interchanging vertices and faces.

42.9 The Dual of the Dual

For a connected plane graph $G$ , the dual of the dual is naturally isomorphic to the original graph:

(G^\ast)^\ast \cong G.

The reason is geometric. The faces of $G^\ast$ correspond to the vertices of $G$ . Each edge of $G^\ast$ crosses exactly one edge of $G$ , so taking the dual again restores the original edge correspondence.

This statement depends on using the embedded dual. The dual graph is not only an abstract graph; it inherits an embedding from the construction.

42.10 Dependence on the Embedding

The dual graph depends on the plane embedding of $G$ . A planar graph may have non-equivalent embeddings, and those embeddings may produce non-isomorphic dual graphs.

For highly connected planar graphs, the embedding is more rigid. In particular, 3-connected planar graphs have essentially unique embeddings on the sphere, so their duals are unique up to isomorphism.

This is why one usually defines $G^\ast$ for a plane graph rather than for a planar graph. The embedding is part of the input.

42.11 Cycles and Cuts

Duality turns cycles into cuts.

A cycle in $G$ forms a closed curve in the plane. By the Jordan curve theorem, it separates the plane into an inside and an outside. The dual edges crossing the cycle are exactly the edges that connect the dual vertices inside the curve to the dual vertices outside the curve.

Thus a simple cycle in $G$ corresponds to a cut in $G^\ast$ .

Conversely, a cut in $G$ corresponds to a cycle-like structure in $G^\ast$ .

This principle is called cycle-cut duality. It is one of the main reasons planar duality is useful in network flow, electrical networks, matroid theory, and planar algorithms.

42.12 Spanning Trees and Dual Spanning Trees

Duality also relates spanning trees.

Let $G$ be a connected plane graph, and let $T$ be a spanning tree of $G$ . Consider the set of edges not in $T$ :

E(G) \setminus E(T).

Take the duals of these edges:

\{e^\ast : e \in E(G) \setminus E(T)\}.

These dual edges form a spanning tree of $G^\ast$ .

Thus a spanning tree in the primal graph corresponds to the complementary spanning tree in the dual graph. The tree edges of $G$ and the tree edges of $G^\ast$ partition the common edge set by duality.

42.13 Duality and Maps

Dual graphs give a formal way to move between regions and adjacencies.

If $G$ is the boundary graph of a map, then the dual graph has one vertex for each region. Two dual vertices are adjacent when the corresponding regions share a boundary edge.

This is the graph used in map coloring. Coloring the regions of a map is equivalent to coloring the vertices of its dual graph.

In this way, planar duality connects face coloring and vertex coloring.

42.14 Duality and Polyhedra

Planar duality also appears in convex polyhedra. The cube and the octahedron are dual. The dodecahedron and the icosahedron are dual. The tetrahedron is self-dual.

In a polyhedral dual, faces become vertices and vertices become faces. Edges correspond to edges. This is the same pattern as planar graph duality.

If a polyhedron is projected onto the plane, its skeleton becomes a plane graph. The skeleton of the dual polyhedron corresponds to the dual graph of that plane graph.

42.15 Applications

Dual graphs appear in several areas.

Area	Use of duality
Map coloring	Regions become vertices
Network flow	Cuts and cycles are exchanged
Electrical networks	Mesh and node formulations are related
Computational geometry	Voronoi diagrams and Delaunay triangulations are dual
Planar algorithms	Face traversal and separator methods use embeddings
Matroid theory	Graphic and cographic structures are related

The construction is simple, but its consequences are broad. It changes local face adjacency into ordinary vertex adjacency, and it often turns one difficult problem into a more convenient dual problem.

42.16 Summary

The dual graph $G^\ast$ of a connected plane graph $G$ is formed by placing one dual vertex in each face of $G$ and one dual edge across each edge of $G$ . Vertices and faces are interchanged, while edges are preserved.

The main correspondences are:

$G$	$G^\ast$
Vertex	Face
Face	Vertex
Edge	Edge
Bridge	Loop
Loop	Bridge
Cycle	Cut
Spanning tree	Complementary dual spanning tree

Duality depends on the embedding. It is therefore a construction for plane graphs, not just abstract planar graphs. It provides one of the most powerful tools in planar graph theory because it converts statements about faces into statements about vertices, and statements about cycles into statements about cuts.