Constructing Duals of Embedded Graphs

From an Embedding to a Dual

A plane graph is a graph together with a particular drawing in the plane in which edges meet only at common endpoints. The same abstract graph can have different embeddings, and its faces depend on the chosen embedding. Constructing a dual therefore starts with the drawing, not just the vertex and edge lists. It is often convenient to regard the plane as the sphere with one point removed; this lets us treat the unbounded region in the plane as an ordinary face.

All primal graphs in this tutorial are finite and simple, but a dual can have loops or repeated edges. For each edge of the embedded graph, the dual records which face lies on one side and which face lies on the other. Keep the primal edge as a label on its dual edge: labels make it possible to check that no edge has been omitted or counted twice.

Definition: Given a plane embedding of \(G\), its plane dual \(G^*\) has one vertex \(f^*\) for each face \(f\) of the embedding. For every primal edge \(e\), add one dual edge \(e^*\) joining the vertices corresponding to the faces on the two sides of \(e\). If those sides belong to the same face, \(e^*\) is a loop. If different primal edges have the same pair of incident faces, their dual edges are kept as distinct edges.

A face is a connected region of the complement of the drawing. Its boundary need not be a simple cycle: a boundary walk can repeat vertices or edges, and a face can have more than one boundary walk. In particular, boundary walks are useful for recording edge-sides, but they are not a substitute for identifying the actual regions of the complement.

A Step-by-Step Construction

For an explicit drawing, the most dependable method is to label the faces first and then process each edge once. When the embedding is specified by the cyclic order of edges around each vertex, boundary tracing provides a systematic way to record the edge-sides. At an isolated vertex there are no incident edge-sides to trace; identify the faces directly from the embedding instead.

List the vertices and edges.
Write \(V(G)\) and \(E(G)\), and make clear which drawing or cyclic orders specify the embedding.

Identify and label the faces.
Use the regions of the drawing. Record boundary walks for the edge-sides, but group walks that belong to the same region. Handle isolated vertices or an edgeless graph by identifying the complementary regions directly.

Inspect both sides of each edge.
For each \(e\in E(G)\), record the face on each side. The two faces may be the same.

Create and label the dual edge.
Add one edge \(e^*\) between the corresponding dual vertices, retaining the label \(e\). Do not merge edges merely because they have the same endpoints.

Check the result.
There must be one dual vertex per face and one labelled dual edge per primal edge. Check each edge’s two face labels against the embedding.

Here is the boundary-tracing rule when the embedding is given by cyclic orders. Replace each edge \(uv\) by two directed versions, \((u,v)\) and \((v,u)\), called darts. To trace a side of a face, arrive at a vertex along a dart, reverse direction, and take the next dart in the cyclic order at that vertex, consistently choosing the same direction of turn throughout. This rule gives a successor for every dart. Since there are finitely many darts and each has exactly one successor and one predecessor, the rule partitions the darts into closed tracing walks. Each walk records a boundary component of a face. If the graph is disconnected, distinct walks can border the same face, so use the embedding to group them by region.

Why the procedure works: Each edge has two local sides in the embedding, and each side lies in a face. The construction adds exactly one dual edge whose endpoints are precisely those two face labels. Boundary tracing records the sides consistently: at a vertex, the cyclic order specifies which edge-side follows the one just traversed along the boundary. The successor rule is a permutation of the darts, so every dart-side is included in exactly one tracing orbit. Grouping these orbits by the complementary region assigns every recorded side to its actual face. Isolated vertices contribute no darts, so their faces must be identified directly. Thus the procedure reproduces the edge-to-face incidence in the definition of \(G^*\). \(\square\)

Worked Examples

Worked Example: The Dual of an Embedded Cycle

Let \(G\) have \(V(G)=\{1,2,3,4\}\) and \(E(G)=\{12,23,34,41\}\). Embed the vertices in this order around a circle, with each edge drawn as a side of the circle. The embedding has two faces: \(f_{\mathrm{in}}\), inside the circle, and \(f_{\mathrm{out}}\), outside it. The inside boundary walk is \(1,2,3,4,1\); the outside boundary walk traverses the same edges in the reverse direction, \(1,4,3,2,1\).

For each of the four primal edges, one side borders \(f_{\mathrm{in}}\) and the other side borders \(f_{\mathrm{out}}\). Thus the dual has \(V(G^*)=\{f_{\mathrm{in}}^*,f_{\mathrm{out}}^*\}\). Its labelled edges are \(12^*,23^*,34^*,41^*\), each joining those two vertices. These are four distinct edges with the same endpoints.

Check: The embedding has two regions, so the dual has \(2\) vertices. The primal edge list has \(4\) edges, and processing the list gives exactly \(4\) dual edges. Each has one endpoint \(f_{\mathrm{in}}^*\) and one endpoint \(f_{\mathrm{out}}^*\), matching the two sides of its primal edge.

Worked Example: The Dual of an Embedded Tree

Let \(G\) have \(V(G)=\{1,2,3,4\}\) and \(E(G)=\{12,23,34\}\), embedded as a straight path in that order. The complement of this drawing in the plane is connected: a route between points on either side of the path can be made by going around one of its free ends. Hence there is one face, \(f\). Its boundary tracing walk is \(1,2,3,4,3,2,1\); each path edge is encountered on both sides of this single face.

The dual therefore has \(V(G^*)=\{f^*\}\). The side labels of edge \(12\) both name \(f\), so \(12^*\) is a loop at \(f^*\). The same is true for \(23\) and \(34\). Thus \(E(G^*)=\{12^*,23^*,34^*\}\), with all three edges loops at the one dual vertex.

Check: The primal edge list has \(3\) entries, and the dual construction gives one labelled edge for each, hence \(3\) dual edges. The face list has one entry, hence \(1\) dual vertex. The repeated appearance of an edge in the boundary walk does not create another dual edge: the dual edge is added once per primal edge, not once per traversal in a boundary walk.

Worked Example: The Dual of a Tetrahedral Embedding

Let \(G\) have \(V(G)=\{1,2,3,4\}\) and \(E(G)=\{12,13,14,23,24,34\}\). Embed \(G\) as the edges of a tetrahedron on the sphere. Its four faces have boundary walks \(1231\), \(1241\), \(1341\), and \(2342\); name them \(A,B,C,D\), respectively.

Now inspect each edge’s two incident faces. Edge \(12\) separates \(A\) and \(B\); \(13\) separates \(A\) and \(C\); \(14\) separates \(B\) and \(C\); \(23\) separates \(A\) and \(D\); \(24\) separates \(B\) and \(D\); and \(34\) separates \(C\) and \(D\). Therefore \(V(G^*)=\{A^*,B^*,C^*,D^*\}\), and the labelled dual edges are \(12^*:A^*B^*\), \(13^*:A^*C^*\), \(14^*:B^*C^*\), \(23^*:A^*D^*\), \(24^*:B^*D^*\), and \(34^*:C^*D^*\).

Check: There are \(4\) listed faces, so the dual has \(4\) vertices. The six primal edges give \(6\) dual edges. Their endpoint pairs are \(AB,AC,BC,AD,BD,CD\), which are all the pairs of distinct vertices among \(A,B,C,D\). Thus in this embedding the dual is another \(K_4\). Each dual vertex has degree \(3\): for example, \(A^*\) is incident with the edges labelled \(12,13,23\), so its degree is \(3\), and the same count applies to \(B^*,C^*,D^*\).

Special Care with Empty Edge Lists

Boundary tracing works with darts, so it only records sides of edges. If there are no edges, there are no darts and no tracing walks. That does not mean that the embedding has no faces: the faces are regions of the complement, and must be found from the embedding itself.

Worked Example: One Isolated Vertex

Let \(G\) have \(V(G)=\{x\}\) and \(E(G)=\varnothing\), embedded as one point in the plane. The complement of one point in the sphere is connected, so the embedding has one face, \(f\). There are no edge-sides and no boundary walks to trace. Identify the face directly from the complement.

The dual has \(V(G^*)=\{f^*\}\) and \(E(G^*)=\varnothing\), because there is one face and no primal edge to produce a dual edge.

Check: The primal edge list has \(0\) entries, so the dual edge list must also have \(0\) entries. The one complementary region gives exactly \(1\) dual vertex. In particular, counting boundary walks would incorrectly give no faces; the face is determined by the embedding, not by the existence of an edge-boundary walk.

Common Pitfalls and Checks

Do not equate boundary walks with faces. A walk records how edge-sides are encountered; it is not automatically a distinct face. In the path example, traversing each edge twice does not create extra faces, and in an embedding with isolated vertices the face list can contain regions even though no boundary walks are available. Determine regions from the embedding and then associate boundary walks with them.

Do not add one dual vertex per boundary walk. For disconnected embeddings, more than one boundary walk can border the same region. The dual has one vertex for each face, meaning each connected region of the complement. Use the drawing or an equivalent explicit specification of the regions to group walks correctly.

Do not merge dual edges with identical endpoints. In the cycle example, all four primal edges separate the same two faces. They produce four separate labelled dual edges, not one. More generally, preserve the one-to-one correspondence between the primal edge list and the dual edge list.

Do not assume the two sides of an edge belong to different faces. In the embedded path example, both sides of every edge lie in the same face, so the corresponding dual edges are loops. The construction uses the face on each side, even when those face labels agree.

Construction checklist: Before accepting a proposed dual, verify that every face appears exactly once as a dual vertex; every primal edge has exactly one labelled dual edge; the endpoints of that dual edge are the faces on the two sides of the primal edge; and every repeated edge or loop required by those incidences has been retained.

Check Your Understanding

For each question, use the specified embedding as well as the abstract edge list.

For the cycle with edges \(12,23,34,41\) embedded around a circle, list the two faces and state the endpoints of each labelled dual edge.
In the embedded path with edges \(12,23,34\), why does the boundary walk traversing an edge twice produce only one dual edge for that primal edge?
Suppose a plane embedding has \(5\) faces and \(7\) primal edges. How many vertices and labelled edges does its dual have? Explain which part of the construction gives each count.
For one isolated vertex embedded in the plane, identify the face and write the dual’s vertex and edge sets.
Why can a list of boundary walks alone be insufficient to decide how many dual vertices to create in a disconnected embedding?