Faces and Boundary Walks

Faces as Regions of the Complement

A plane embedding is a drawing of a graph in the plane in which vertices are distinct points and edges are arcs joining their endpoints. The interior of an edge contains no vertex, and edge interiors do not intersect one another. The drawing itself is a subset of the plane; write it as \(|G|\). A face is not an extra part of the graph: it is a connected region left after the drawing is removed.

Equivalently, one may regard the drawing as embedded on the sphere by adding a point at infinity. The face containing that point corresponds to the unbounded face in the plane. Faces are open connected regions, whereas their boundaries may contain vertices and edges of the drawing. In particular, a face and a boundary walk are different kinds of objects: a face is a region, while a boundary walk is a way of tracing along edge sides.

Proof. Since the graph is finite and each of its finitely many edges is drawn as a bounded arc, the entire drawing \(|G|\) is contained in some closed disk \(D\). The exterior \(\mathbb{R}^2\setminus D\) is connected and disjoint from \(|G|\), so it lies in one component of \(\mathbb{R}^2\setminus |G|\). That component is unbounded, which proves existence. Any unbounded face must meet \(\mathbb{R}^2\setminus D\); otherwise it would be contained in \(D\) and hence bounded. Since the exterior is contained in a single component, every unbounded face is that same component. Thus the unbounded face is unique. If the graph has no vertices or edges, its drawing is empty and the whole plane is the single, unbounded face, so the argument also covers that case. \(\square\)

A basic topological fact used in the examples is the Jordan curve theorem: a simple closed curve in the plane separates the plane into a bounded interior and an unbounded exterior, with the curve as their common boundary. This is a standard result from topology; its proof is beyond this tutorial. For polygonal drawings, it lets us identify the regions by looking at the closed curves in the embedding.

Tracing a Face Along Edge Sides

A walk is a sequence of vertices in which consecutive vertices are joined by an edge; vertices and edges may repeat. It is closed if its first and last vertices agree. A facial walk is a closed walk obtained by tracing edge sides while keeping the same face on one fixed side, say the left. It is not required to be a path or a cycle: either vertices or edges may occur more than once.

Here is why edge-side tracing produces closed walks. Give the drawing an orientation by choosing which side is called left. At a vertex, the incident edges have a circular order around that vertex. If we arrive along a directed edge and keep a specified face on the left, the next edge is the one adjacent to the same local sector of that face. This determines one next directed edge. Reversing the rule determines a unique preceding directed edge.

Proof. A directed edge records a traversal of one edge in one direction, and therefore records one of its two sides as the side on the left. At its terminal vertex, the circular order of incident edges determines a unique outgoing directed edge that continues along the boundary of the same local face sector. Thus each directed edge has a unique successor. The local circular order also gives a unique predecessor for every directed edge, so the successor rule is a bijection on the finite set of directed edges. Iterating a bijection on a finite set eventually returns to the starting directed edge; because each element has a unique predecessor, the resulting orbit is a cycle of directed edges. Reading the endpoints of that orbit gives a closed walk. Each orbit traces one edge-side boundary component with the chosen face on the left. \(\square\)

This lemma describes how edge sides are traced; it does not say that every point on a face boundary is represented by a walk. An isolated vertex has no incident edge side and cannot appear in an edge-traced walk, even if it lies on the boundary of a face. Also, when a graph is disconnected, a single face can have several distinct boundary components, and hence several facial walks associated with it.

Worked Examples in Explicit Embeddings

Reading Boundary Descriptions Carefully

When describing a face in an embedding, first specify the region and then give the walk or walks that trace its edge-incident boundary. For a connected drawing made of closed curves, the unbounded face is the region outside the outermost curve. With nested components, the region between two curves meets both, so its boundary description has one walk for each curve. Isolated vertices require separate mention because they can lie on a face boundary without belonging to any edge-traced walk.

A walk records an ordered traversal, not merely a set of boundary points. Reversing a walk changes which side is on the left. A facial walk may repeat a vertex, and in some embeddings an edge can be traversed in both directions as part of one boundary tracing. For example, a single drawn edge has two sides and the boundary tracing goes from one endpoint to the other and back. That closed walk has length two; it is a walk, not a cycle. The simple-graph condition forbids loops and multiple edges in the graph, but it does not prevent a boundary walk from repeating an edge.

Common Pitfall: Replacing the Boundary by the Walk

For the isolated-vertex example, a tempting but wrong calculation is: “There are \(|E(G)|=0\) edges, so the total length of the facial walks is \(0\), and therefore the face boundary is empty.” The first two statements correctly describe edge tracing, but the conclusion does not follow: the boundary is \(\{p\}\), not the empty set. A walk records edge-side traversals only; a face boundary is a topological set and may also contain isolated vertices. Conversely, a face can have more than one boundary walk, as the region between the nested square and triangle demonstrates. Always identify the face as a complementary region before describing its boundary.