Defining the Plane Dual

Why the Embedding Is Part of the Definition

An abstract planar graph records vertices and edges, but it does not record where those edges are drawn. A plane graph includes that drawing: it specifies how the edges sit in the plane and, consequently, which regions they enclose. The plane dual is built from those regions and from the way each edge separates—or fails to separate—the regions on its two sides. Thus the dual is defined from an embedding, not merely from an abstract graph.

Throughout, a graph is finite and simple unless stated otherwise. A plane embedding of \(G=(V,E)\) places distinct points for the vertices in the plane and draws each edge as a curve between its endpoints, with edge interiors disjoint from all vertices and from the interiors of other edges. The resulting drawing is a plane graph. A face is a connected component of the plane after the drawing is removed; the unbounded component is also a face.

Definition: Let \(G\) be a plane graph. Its plane dual \(G^*\) has one vertex for each face of \(G\). For each edge \(e\) of \(G\), draw one dual edge \(e^*\) that crosses \(e\) once and no other primal edge. The endpoints of \(e^*\) are the vertices corresponding to the faces on the two sides of \(e\). If both sides of \(e\) belong to the same face, \(e^*\) is a loop. The dual is generally a multigraph: different primal edges can give parallel dual edges.

Here “crosses once” describes the local passage through the interior of the primal edge. Away from that crossing, a dual edge runs through the incident face regions to its endpoint vertices. The crossing is made transverse, so locally one side of the primal edge lies in each of its two sides. Those sides may belong to the same face; the definition does not require two distinct incident faces.

For a connected plane graph with at least one edge, the boundary of each face can be traced by following edge-sides, producing a closed boundary walk. A walk may repeat vertices or edges, so it need not be a cycle. There is one exception to this description: the graph \(K_1\), with one vertex and no edges, has one face, but there is no edge-side to follow. Its dual has one vertex and no edges.

What Embedding Data Determines the Dual?

For each primal edge, the crucial information is the identity of the face on each side. A complete specification of the plane embedding supplies that information. For a connected plane graph with edges, one can record it by the face boundary walks, with the edge-sides distinguished; for disconnected plane graphs, the relative placement of components also matters. Merely giving the abstract vertex and edge sets does not in general say which faces are incident with an edge.

Proposition: If two plane embeddings have the same face-edge incidence data up to relabeling their faces, then their abstract dual multigraphs are isomorphic. The data meant here records, for every primal edge, the two incident faces, allowing those faces to coincide.

Proof. Suppose the faces in the first embedding are matched bijectively with the faces in the second, and each primal edge has the same pair of incident faces under this matching. Map each dual vertex to the vertex for the matched face. For every primal edge \(e\), map its dual edge in the first dual to the dual edge corresponding to \(e\) in the second. Its endpoints match because the two incident faces of \(e\) match; this also preserves a loop when the two faces coincide. Every dual vertex and edge is obtained in this way, so the map is an isomorphism of multigraphs. \(\square\)

This proposition concerns the abstract dual. To specify the dual as a plane graph as well, retain its embedding, with each dual edge passing through its corresponding primal edge. The distinction is important: an abstract dual can have the same vertices and edges under different drawings, while a plane dual records where those edges lie.

Worked Examples

Worked Example: A Square with a Diagonal

Let \(G=(V,E)\), where \(V=\{1,2,3,4\}\) and \(E=\{12,23,34,41,13\}\). Embed \(1,2,3,4\) in that order around a square and draw the diagonal \(13\) inside it. Name the two bounded faces \(f_1\) and \(f_2\), with boundaries \(1,2,3,1\) and \(1,3,4,1\), respectively, and name the outside face \(f_0\).

The dual has vertices \(f_0,f_1,f_2\). Edge \(12\) has \(f_1\) on one side and \(f_0\) on the other, so its dual joins \(f_1\) to \(f_0\). Edge \(23\) has the same two incident faces and gives a second \(f_1f_0\) edge. Edges \(34\) and \(41\) each give an \(f_2f_0\) edge. The diagonal \(13\) separates the two bounded faces, so it gives an \(f_1f_2\) edge.

Check: the five primal edges give exactly five dual edges: two between \(f_0\) and \(f_1\), two between \(f_0\) and \(f_2\), and one between \(f_1\) and \(f_2\). The face incidences are consistent with the drawing: the diagonal is the only edge between the two bounded faces, and each of the four boundary edges has the outside face on one side.

Worked Example: A Path Whose Dual Has Loops

Let \(G=(V,E)\), where \(V=\{1,2,3\}\) and \(E=\{12,23\}\), embedded as a straight path in the plane. Its complement has one face, which we call \(f\). Each edge has \(f\) on both sides. Therefore \(G^*\) has one vertex \(f\), and each of the two primal edges gives a loop at \(f\).

Check: there are two primal edges, so there are two dual edges, both loops. There is only one face vertex because the path encloses no region: points on either side of either edge can be joined through the complement around an endpoint. In particular, it would be incorrect to invent a second dual vertex by treating the two sides of an edge as different faces.

Worked Example: The Same Abstract Graph, Different Embeddings

Let \(G=(V,E)\) consist of two disjoint triangles, with \(V=\{1,2,3,4,5,6\}\) and \(E=\{12,23,31,45,56,64\}\). First embed one triangle inside the other, with no edges between them. There are three faces: \(f_0\) outside the outer triangle, \(f_1\) between the triangles, and \(f_2\) inside the inner triangle. Each of \(12,23,31\) separates \(f_0\) from \(f_1\), and each of \(45,56,64\) separates \(f_1\) from \(f_2\). The dual therefore has three parallel \(f_0f_1\) edges and three parallel \(f_1f_2\) edges.

Now embed the same two triangles side by side, not nested. There are again three faces: the common outside face \(g_0\) and the two triangle interiors \(g_1,g_2\). Each edge of \(12,23,31\) separates \(g_0\) from \(g_1\); each edge of \(45,56,64\) separates \(g_0\) from \(g_2\). The dual has three parallel \(g_0g_1\) edges and three parallel \(g_0g_2\) edges.

Check: both embeddings have three faces and six primal edges, so each dual has three vertices and six edges. In the nested embedding, all six dual edges join consecutive vertices in the sequence \(f_0,f_1,f_2\). In the side-by-side embedding, every dual edge is incident with \(g_0\). These incidence descriptions differ, so the same abstract graph can have nonisomorphic abstract duals when embedded differently.

Two Basic Facts About the Construction

Theorem: For a plane graph \(G\), the construction gives a one-to-one correspondence between the edges of \(G\) and the edges of \(G^*\). In particular, \(|E(G^*)|=|E(G)|\). This includes dual loops and parallel edges.

Proof. By definition, one dual edge is assigned to each primal edge, and no dual edge is assigned to two different primal edges. Conversely, every edge of the dual is introduced for a primal edge. Thus the assignment is a bijection between the two edge sets, and their cardinalities are equal. The argument does not require distinct endpoints in the dual: if the incident faces coincide the corresponding edge is a loop, and if several primal edges have the same pair of incident faces their dual edges remain distinct. \(\square\)

The same definition gives a face-to-vertex correspondence: there is one dual vertex for each face, including the unbounded face. For \(K_1\), this means one dual vertex and zero edges, as noted above. This convention avoids treating the absence of edge-sides as evidence that the graph has no face.

Common Mistakes

Confusing an edge-side with a face. A primal edge has two local sides, but those sides need not belong to two different faces. In the path example, the incorrect calculation “two sides per edge, so two dual vertices” counts sides instead of faces. The correction is to identify the connected components of the complement: the path has one face, so both sides of each edge lead to the same dual vertex and each dual edge is a loop.

Forgetting that the unbounded region is a face. In the square example, omitting \(f_0\) would leave the dual edges of \(12,23,34,41\) without their correct outside endpoint. The dual uses all faces, bounded and unbounded.

Discarding embedding information. A list of vertices and edges alone does not specify whether components are nested or side by side. Since these placements can change the incident faces of edges, they can change the dual. When defining a plane dual, state the embedding or give enough face-edge incidence data to recover it.

Check Your Understanding

Use the face-incidence definition in each question; when a graph is embedded, include the unbounded face.

For the plane graph with \(V=\{1,2,3\}\) and \(E=\{12,23,31\}\), embedded as a triangle, name its faces and describe the endpoints of each dual edge.
Can a dual edge be a loop when the corresponding primal edge is not a loop? Explain using the definition.
Why does the plane dual of \(K_1\) have a vertex even though there are no primal edges?
What embedding information distinguishes nested disjoint triangles from side-by-side disjoint triangles?
If a plane graph has seven edges, how many edges does its dual have, counting loops and parallel edges separately?

What You'll Learn