Faces and Their Boundary Walks
A face of a plane graph is a region of the plane left after the graph has been drawn. It is tempting to think that the boundary of each face is a cycle, but this is not generally true. A boundary may pass through a vertex more than once, traverse an edge in both directions, or consist of several separate boundary walks. These features matter when constructing the dual: dual vertices represent faces, not individual boundary walks.
Throughout, a plane graph is a finite graph drawn in the plane so that vertices are distinct points and edges meet only at common endpoints. A face is a connected component of the complement of the drawing. The unbounded component is the outer face. To trace a face boundary, follow an edge while keeping the face on a fixed side, and at each vertex continue along the edge that borders the same local region. The cyclic order of incident edges around each vertex determines this continuation.
Here a walk may repeat vertices and edges; a cycle, by contrast, has distinct vertices apart from its repeated start and end. The boundary-walk convention records edge-sides: for each edge there are two sides to trace, one for each direction of traversal. A bridge has the same face on both sides, so its two directions can occur in the same facial walk. If the graph is disconnected, tracing around different components can give distinct walks belonging to the same face. In particular, the outer face need not have just one boundary walk.
Proof. First suppose there is at least one edge. Give each edge its two possible directions of traversal. For each directed edge, keep the face on the same side as the edge is traversed. At the endpoint, the cyclic order of the incident edges specifies which outgoing edge borders that same local sector of the face. Thus every directed edge has a uniquely determined successor in the tracing process. Each directed edge also has a unique predecessor, by tracing the same local rule backwards. So the successor rule is a permutation of the finite set of directed edges. Iterating a permutation on a finite set returns to the starting directed edge, producing a closed sequence of edges and hence a closed walk. A walk can revisit a vertex, and it can use both directions of a bridge; neither possibility prevents the tracing from closing. Different closed walks can border the same face, for example when the graph has separate components. If there are no edges, there are no edge-sides to trace, so there are no facial boundary walks. \(\square\)
Examples of Repeated and Multiple Boundaries
Worked Example: A Bridge Repeated on the Outer Face
Let \(G\) have vertex set \(V(G)=\{a,b,c,d\}\) and edge set \(E(G)=\{ab,bc,ca,ad\}\). Draw the triangle \(abc\) and draw the edge \(ad\) as a pendant edge extending outward from \(a\). The graph has two faces: the interior of the triangle and the outer face.
The triangular face has boundary walk \(a,b,c,a\). For the outer face, one possible tracing is \(a,c,b,a,d,a\). The edge \(ad\) occurs twice in this walk, once in each direction, because it is a bridge and the outer face lies on both sides of it. The outer boundary walk has length \(5\), even though it is not a cycle.
Check: There are \(4\) edges, so the total number of edge-sides is \(2\cdot4=8\). The triangular facial walk uses \(3\) edge-sides, and the outer walk uses \(5\): \(3+5=8\). In particular, counting only the three edges of the outer triangle would miss both traversals of \(ad\).
Worked Example: One Face with Two Boundary Walks
Let \(G\) have vertex set \(V(G)=\{a,b,c,x,y,z\}\) and edge set \(E(G)=\{ab,bc,ca,xy,yz,zx\}\). Draw the triangle \(abc\) and the triangle \(xyz\) in disjoint regions of the plane. There are three faces: the interior of each triangle and the common outer face.
The interior faces have boundary walks \(a,b,c,a\) and \(x,y,z,x\), respectively. The outer face has two boundary walks, one around each triangle: for example, \(a,c,b,a\) and \(x,z,y,x\). These are two separate walks belonging to the same face. Thus even though each boundary walk is closed, one walk does not necessarily describe the full boundary of a face.
Check: The graph has \(6\) edges, hence \(2\cdot6=12\) edge-sides. The two interior walks use \(3+3=6\) edge-sides, and the two outer walks use another \(3+3=6\). The total \(6+6=12\) accounts for every side exactly once.
Why the Dual Is Connected
For a plane graph \(G\), its dual \(G^*\) has one vertex for each face of \(G\). Each edge \(e\) of \(G\) gives a dual edge joining the vertices corresponding to the faces on the two sides of \(e\). If both sides belong to the same face, the dual edge is a loop. Distinct primal edges can give parallel dual edges. Neither loops nor parallel edges affect whether distinct vertices of a graph can be joined by paths.
Proof. Let \(F\) and \(H\) be any two faces of \(G\). Choose a point \(p\) in \(F\) and a point \(q\) in \(H\). We will find a walk in \(G^*\) from the dual vertex for \(F\) to the dual vertex for \(H\).
Join \(p\) to \(q\) by a curve in the plane that avoids all graph vertices and crosses edges only finitely many times, at interior points of edges. Such a curve can be chosen by a small perturbation of a polygonal route: there are finitely many vertices and edges, so the route can be adjusted to avoid vertices and to cross the drawn edges rather than run along them. List the faces encountered along the route, in order, starting with \(F\) and ending with \(H\). Whenever the route crosses a primal edge \(e\), it passes between the faces on the two sides of \(e\). In the dual, those two faces are joined by the edge \(e^*\). Therefore, the sequence of crossings gives a walk in \(G^*\) from \(F\) to \(H\). If a crossed edge has the same face on both sides, its dual is a loop; that crossing does not change the current dual vertex. Since \(F\) and \(H\) were arbitrary, every pair of dual vertices is joined by a walk, and thus by a path. Hence \(G^*\) is connected. This argument does not require a path in \(G\) between any of its components. \(\square\)
The geometric reason is that a route in the plane can travel between any two regions, crossing graph edges as needed. The dual records each such crossing as a step between face-vertices. This is why dual connectivity does not depend on connectivity of the primal graph. A graph with no edges has one face, so its dual has one vertex and is connected as well.
Worked Example: The Dual of Two Disjoint Cycles
Use the graph from the previous example: \(V(G)=\{a,b,c,x,y,z\}\) and \(E(G)=\{ab,bc,ca,xy,yz,zx\}\), with the two triangles drawn in disjoint regions. The primal graph has two connected components. Name its faces \(O,I_1,I_2\), where \(O\) is the outer face and \(I_1,I_2\) are the interiors of \(abc\) and \(xyz\).
The three edges \(ab,bc,ca\) each have \(O\) on one side and \(I_1\) on the other, so their three dual edges all join \(O\) to \(I_1\). The three edges \(xy,yz,zx\) each have \(O\) on one side and \(I_2\) on the other, so their three dual edges all join \(O\) to \(I_2\). Thus the dual has three vertices and six edges, with parallel edges between \(O\) and each of \(I_1,I_2\). It is connected: \(I_1\) is adjacent to \(O\), and \(I_2\) is adjacent to \(O\), so \(I_1,O,I_2\) is a path.
Check: There are \(6\) primal edges, and the construction gives \(3+3=6\) dual edges. The dual’s two interior-face vertices connect through the outer-face vertex, even though no primal edge joins the two triangles.
Worked Example: A Dual with One Vertex
Let \(G\) have vertex set \(V(G)=\{p,q,r,s\}\) and edge set \(E(G)=\{pq,rs\}\), drawn as two disjoint straight segments. The complement of these two segments is one face \(O\). Each segment has \(O\) on both sides, so each gives a loop at the dual vertex \(O\). Hence \(G^*\) has one vertex and two loops.
Check: A graph with one vertex is connected: the only vertex is joined to itself by a path of length \(0\). The two loops do not create additional dual vertices, and they do not interfere with connectivity.
Common Pitfalls and Why They Matter
Do not replace “boundary walk” by “cycle.” In the bridge example, the outer facial walk \(a,c,b,a,d,a\) repeats \(a\) and traverses \(ad\) twice. Calling it a cycle would incorrectly exclude a valid boundary tracing and would lose one of the two edge-sides of the bridge. The correction is to record the entire closed walk, including repeated vertices and edge traversals.
Do not identify faces with boundary walks. In the two-triangle example, the outer face has two boundary walks but represents only one dual vertex. Counting each of those walks as a separate face would give the wrong dual. Instead, faces are the connected regions of the complement, and their boundary walks describe how the graph borders those regions.
Do not infer that the dual must be disconnected from a disconnected primal graph. The two disjoint triangles have no primal path between their components, yet their dual vertices are connected through the outer face. A route through the plane, not a route along primal edges, is what establishes dual connectivity.
Check Your Understanding
Use the definitions and arguments above to answer the following questions.
- Why can a bridge appear twice in a facial boundary walk?
- Give an example of a face with more than one boundary walk, and explain why those walks do not give separate dual vertices.
- In the graph with \(V(G)=\{a,b,c,d\}\) and \(E(G)=\{ab,bc,ca,ad\}\), which edge is traversed twice by the outer facial walk?
- Explain how a curve crossing primal edges produces a walk in the dual.
- Why does the dual of a plane graph with no edges still satisfy the connectivity conclusion?