Chapter 39. Faces and Regions

A plane graph divides the plane into connected regions. These regions are called faces. The term face includes both the bounded regions enclosed by cycles and the unbounded region outside the drawing. The unbounded region is called the outer face.

Faces belong to a particular embedding. The same abstract planar graph may be drawn in different ways, and the arrangement of its faces may change. Once an embedding is fixed, however, the faces are well-defined objects of the plane graph.

39.1 Regions of the Plane

Let $G$ be a plane graph. The drawing of $G$ consists of points for vertices and curves for edges. Remove these points and curves from the plane. The remaining set breaks into connected regions. Each such region is a face.

For example, a cycle $C_n$ separates the plane into two regions:

Region	Description
Interior face	The bounded region inside the cycle
Outer face	The unbounded region outside the cycle

Thus a triangle has two faces, not one. The outside of the triangle is counted as a face.

A tree has one face. Since a tree has no cycle, it encloses no bounded region. The whole plane around the tree forms a single outer face.

39.2 Bounded and Unbounded Faces

Every finite plane graph has exactly one unbounded face. This is the outer face. All other faces, if any, are bounded.

The distinction depends on the drawing in the plane. If the graph is drawn on a sphere, no face is naturally outer. Choosing an outer face is equivalent to choosing where the sphere is projected onto the plane.

This observation is useful because it shows that the outer face is not mathematically inferior to the bounded faces. It is counted in Euler’s formula and participates in duality just like every other face.

39.3 Face Boundaries

The boundary of a face consists of the vertices and edges encountered when walking around that face. This boundary is often recorded as a closed walk, called a facial walk.

For a simple cycle

v_1v_2\cdots v_nv_1,

there are two facial walks, one for the inner face and one for the outer face. They use the same edges but in opposite directions.

In a more complicated plane graph, the boundary of a face may repeat a vertex or an edge. This happens when bridges are present. A bridge has the same face on both sides, so it is counted twice in the boundary walk of that face.

39.4 Face Degree

The degree of a face is the number of edge appearances on its boundary.

If a face boundary is a triangle, its degree is $3$ . If it is bounded by a square, its degree is $4$ . If an edge appears twice on the boundary, both appearances are counted.

For every connected plane graph,

\sum_{F} \deg(F) = 2e.

The sum is taken over all faces $F$ . The reason is that every edge has two sides. Each side borders a face. Sometimes the two sides border two different faces. Sometimes, for a bridge, both sides border the same face. In both cases, the edge contributes exactly two face-boundary appearances.

39.5 Examples

Consider a triangle. It has

v = 3,\qquad e = 3,\qquad f = 2.

Both faces have degree $3$ . Hence

\sum_F \deg(F) = 3 + 3 = 6 = 2e.

Now consider a square with one diagonal. It has three faces: two triangular bounded faces and one quadrilateral outer face.

The face degrees are

3,\quad 3,\quad 4.

Their sum is

3 + 3 + 4 = 10.

Since the graph has $5$ edges,

2e = 10.

Again,

\sum_F \deg(F) = 2e.

39.6 Faces in Trees

A tree with $v$ vertices has

e = v - 1

and only one face. That single face is the outer face.

The degree of this face is

2e.

This may seem surprising at first. The reason is that each edge of a tree is a bridge. When tracing the boundary of the only face, each edge is traversed once in each direction.

For example, a path with three vertices has two edges. It has one face. The boundary walk goes along one side of the path and returns along the other side. Thus the face degree is

4 = 2e.

39.7 Faces and Cycles

Cycles are what create bounded faces. A graph with no cycles is a forest, and a plane drawing of a forest has no bounded face. A connected forest is a tree, so it has one face.

Adding an edge between two existing vertices of a connected plane graph may create a cycle. If the edge can be drawn inside one existing face without crossing other edges, it splits that face into two faces.

Thus the edge count and face count increase together:

e \mapsto e + 1, \qquad f \mapsto f + 1.

This is the local mechanism behind Euler’s formula. Adding a cycle edge subdivides a region, so $v - e + f$ remains unchanged.

39.8 Faces and Euler’s Formula

For a connected plane graph,

v - e + f = 2.

The face count $f$ includes the outer face. This inclusion is essential.

Solving for $f$ , we get

f = 2 - v + e.

Thus, once $v$ and $e$ are known, the number of faces in a connected plane graph is determined. The embedding may affect the shape and boundary structure of the faces, but the total number of faces is fixed for connected planar embeddings.

For a disconnected plane graph with $c$ connected components,

v - e + f = c + 1.

Equivalently,

f = c + 1 - v + e.

39.9 Inner Faces and Outer Face

In many drawings, the bounded faces are called inner faces. The unbounded face is called the outer face.

Type	Meaning
Inner face	A bounded region of the plane
Outer face	The unique unbounded region
Face boundary	The closed walk around a face
Face degree	Number of edge appearances in the boundary

The outer face often plays a special role in drawings. For example, when drawing a planar graph as a map, the outer face represents the region outside the map. In dual graph construction, however, the outer face still receives a dual vertex.

39.10 Adjacent Faces

Two faces are adjacent if they share an edge on their boundaries.

Sharing only a vertex is not enough. Face adjacency is edge adjacency.

This distinction matters in map coloring. Two regions that meet only at a point do not need different colors under the usual map-coloring rule. Two regions that share a boundary edge must be treated as adjacent.

In the dual graph, adjacent faces of the original plane graph become adjacent vertices in the dual graph.

39.11 Dual Interpretation

Faces become vertices under planar duality. Given a connected plane graph $G$ , its dual graph $G^\ast$ is formed as follows:

Place one vertex inside each face of $G$ . For each edge of $G$ , draw a dual edge crossing it and joining the two dual vertices corresponding to the faces on either side.

This construction shows why faces are structural objects. They are not merely empty regions in a drawing. They determine another graph.

If an edge is a bridge, the same face lies on both sides. In the dual graph, the corresponding dual edge becomes a loop.

39.12 Summary

A face of a plane graph is a connected region of the plane left by the drawing. Every finite plane graph has one outer face and may have several bounded inner faces. Faces are counted in Euler’s formula, and the outer face is included.

The boundary of a face is described by a facial walk. The degree of a face is the number of edge appearances along this walk. For every connected plane graph,

\sum_F \deg(F) = 2e.

Faces connect geometry, topology, and combinatorics. They support Euler’s formula, planar edge bounds, graph duality, map coloring, and planar graph algorithms.