From Face Boundaries to an Embedding
A plane drawing contains more information than its abstract graph: it specifies which regions are faces and how the edges occur around each vertex. For a three-connected planar graph, the boundaries of the faces are cycles. Their cyclic order records enough local information to recover how the edges meet at each vertex, while the cycles themselves specify which edges bound each face. This gives a concrete reconstruction procedure: assemble one polygon per face and glue corresponding sides together.
All graphs in this tutorial are finite and simple. A plane graph is a graph drawn on the sphere with vertices represented by distinct points and edges by arcs that meet only at common endpoints. A face is a connected region of the sphere left after removing the drawing. A facial cycle is a cycle that forms the boundary of a face. The cycle is understood with its cyclic order of vertices and edges, but either direction around it may be listed.
The distinction between a cycle and a facial cycle matters. A cycle divides the sphere into two regions, but either region may contain more of the graph; in that case the cycle does not bound a face. By contrast, every edge of a plane graph has a face on each of its two local sides. Thus, in a three-connected plane graph, each edge occurs in exactly two facial cycles, one for each side.
Recovering the Local Order at a Vertex
The rotation at a vertex is the cyclic order in which its incident edges appear when one goes around the vertex in a small neighborhood. This order is part of the plane embedding. If a facial cycle passes through \(v\) using edges \(e\) and \(f\), then \(e\) and \(f\) are consecutive in the rotation at \(v\): the face occupies the sector between them.
Proof. Let the degree of \(v\) be \(d\). Three-connectivity implies \(d\ge3\). Take a small disk around \(v\) that contains no other vertex and meets each incident edge in one arc. The \(d\) edge-arcs meet the boundary of this disk in \(d\) distinct points, arranged in a circular order. The regions between consecutive arcs are exactly the sectors at \(v\). Each sector belongs to a face, and that face contributes the corner consisting of the two edges on either side of the sector. Therefore the facial-cycle corners give precisely the consecutive pairs in the circular order. Reading these pairs around the circle recovers the order; choosing the opposite direction reverses it. \(\square\)
For a vertex of degree \(d\), there are \(d\) sectors and therefore \(d\) corners, counted around that vertex. The resulting pairs form a cycle on the \(d\) incident edges: each edge is paired with its predecessor and successor. This is local information; to recover the whole spherical embedding, the face cycles must also be assembled consistently across their shared edges.
Gluing the Face Polygons
To reconstruct the embedding, take a polygon for each facial cycle. Label the polygon’s vertices and sides in the order given by that cycle. For every graph edge \(uv\), exactly two facial cycles contain \(uv\). Identify the two polygon sides labelled \(uv\), matching their endpoints labelled \(u\) and \(v\). The polygons then meet along the graph edges, and their vertices and sides give the original graph.
For a consistent orientation, direct every face boundary so that the face lies on the same chosen side as one travels around it. Along a shared edge, the two face boundaries then traverse the edge in opposite directions. This opposite-direction rule is necessary for the polygon interiors to lie on opposite sides of the glued edge. Since the cycle data comes from an embedding on the sphere, such a consistent choice exists: orient the face boundaries using one orientation of the sphere. Reversing that orientation reverses all the boundary directions together.
Proof. Start with the given plane embedding as the reference. Each facial cycle is a simple closed curve. Its face lies on one side of that curve, and the closure of the face is a disk bounded by the cycle. This follows from the Jordan curve theorem and the fact that the facial boundary is a cycle. Assign to each polygon the corresponding closed face disk. When two face closures meet along an edge, their copies of that edge have the same endpoints and lie on opposite sides, so the prescribed side identification matches the two disks exactly as they meet in the embedding. Their vertices are identified according to the labels. Consequently, gluing all the polygons produces the same decomposition into vertices, edges and face disks as the given embedding of the sphere. In particular, the glued surface is a sphere, and the listed cycles are exactly its face boundaries. \(\square\)
This principle reconstructs the embedding from a valid list; it is not a test that an arbitrary list of cycles can be glued to form a sphere. For proposed data, the edge occurrences, local corners and global surface must all be compatible. The examples below use cycle lists known to be the facial cycles of the specified plane graphs.
Worked Example: Recovering the Faces of \(K_4\)
Let \(G\) have \(V=\{1,2,3,4\}\) and \(E=\{12,13,14,23,24,34\}\). Its four facial cycles in a spherical embedding are \(123\), \(124\), \(134\), and \(234\).
At vertex \(1\), the incident edges are \(12,13,14\). The cycles \(123\), \(124\), and \(134\) give the corners \((12,13)\), \((12,14)\), and \((13,14)\), respectively. These pairs recover the circular order \(12,13,14\), or its reversal \(12,14,13\). At vertex \(2\), the incident edges are \(12,23,24\); the listed cycles give all three pairs \((12,23)\), \((12,24)\), and \((23,24)\). The same procedure applies at vertices \(3\) and \(4\).
Now take four triangular polygons, one for each listed cycle. Edge \(12\) occurs in \(123\) and \(124\); edge \(13\) occurs in \(123\) and \(134\); edge \(14\) occurs in \(124\) and \(134\). Likewise, \(23\) occurs in \(123\) and \(234\), \(24\) in \(124\) and \(234\), and \(34\) in \(134\) and \(234\). Glue the two copies of each edge, matching equal-numbered endpoints.
| Check | Calculation |
|---|---|
| Vertices, edges, faces | \(|V|=4,\ |E|=6,\ |F|=4\) |
| Edge-face incidences from faces | \(4\cdot3=12\) |
| Edge-face incidences from edges | \(2\cdot6=12\) |
| Euler check | \(4-6+4=2\) |
Check: Each edge occurs in exactly two listed cycles, and both incidence counts equal \(12\). The Euler calculation gives \(2\), as required for a spherical embedding.
Worked Example: A Triangular Bipyramid
Let \(G\) have \(V=\{a,b,c,x,y\}\) and \(E=\{ab,bc,ca,xa,xb,xc,ya,yb,yc\}\). Its six facial cycles are \(xab\), \(xbc\), \(xca\), \(yab\), \(ybc\), and \(yca\).
At \(a\), the incident edges are \(ab,ac,ax,ay\). The four facial corners there are \((ax,ab)\) from \(xab\), \((ab,ay)\) from \(yab\), \((ay,ac)\) from \(yca\), and \((ac,ax)\) from \(xca\). Together these give the cyclic order \(ax,ab,ay,ac\), up to reversal. At \(b\), the corners from \(xab\), \(xbc\), \(yab\), and \(ybc\) give the cyclic order \(bx,bc,by,ba\), up to reversal.
The remaining vertices each have degree three. At \(x\), the faces \(xab,xca,xbc\) give the pairs of incident edges \(xa\) with \(xb\), \(xa\) with \(xc\), and \(xb\) with \(xc\). At \(y\), the faces \(yab,yca,ybc\) give the corresponding three pairs. Thus all four local rotations are read directly from the face corners.
There are five vertices, nine edges, and six listed faces. Counting edge occurrences through faces gives \(6\cdot3=18\); counting two sides for each edge gives \(2\cdot9=18\). Euler’s formula gives \(5-9+6=2\). These checks agree with the polygon-gluing reconstruction.
Check: The cycles \(xab\) and \(yab\) are the two facial cycles containing edge \(ab\); the same two-sided check holds for each of the other eight edges. The face list therefore accounts for all \(18\) edge-face incidences.
Worked Example: Reconstructing the Cube from Six Squares
Let the vertices be the binary strings of length three, and join two strings when they differ in exactly one coordinate. Thus \(V=\{000,001,010,011,100,101,110,111\}\). Explicitly, the edges are \(000\!-\!001,000\!-\!010,000\!-\!100,001\!-\!011,001\!-\!101,010\!-\!011,010\!-\!110,011\!-\!111,100\!-\!101,100\!-\!110,101\!-\!111,110\!-\!111\).
The six facial cycles are the squares with one coordinate fixed. Listed in cyclic order, they are:
- First coordinate \(0\): \(000,001,011,010\); first coordinate \(1\): \(100,101,111,110\).
- Second coordinate \(0\): \(000,001,101,100\); second coordinate \(1\): \(010,011,111,110\).
- Third coordinate \(0\): \(000,010,110,100\); third coordinate \(1\): \(001,011,111,101\).
At \(000\), name the three incident edges \(e_1=000\!-\!100\), \(e_2=000\!-\!010\), and \(e_3=000\!-\!001\). The face with second coordinate \(0\) gives the pair \((e_1,e_3)\); the face with third coordinate \(0\) gives \((e_1,e_2)\); and the face with first coordinate \(0\) gives \((e_2,e_3)\). These three corners recover the cyclic order of the edges at \(000\). The same face-corner procedure applies at each of the other seven vertices.
There are eight vertices and twelve edges. The six square faces contribute \(6\cdot4=24\) edge-face incidences; the edges contribute \(2\cdot12=24\). Euler’s check is \(8-12+6=2\). Gluing the six square polygons along their matching sides recovers the spherical cell decomposition.
Check: Every listed square has four sides, and every edge of the specified graph changes one coordinate, so it lies in the two squares obtained by fixing either of the other two coordinates. Thus each edge occurs twice in the face list.
Common Pitfall: Not Every Cycle Is a Face
In the triangular bipyramid example, \(abc\) is a cycle: its edges \(ab,bc,ca\) all belong to the graph. But it is not a facial cycle in the displayed embedding. The vertices \(x\) and \(y\), with their incident edges, lie on opposite sides of this cycle. Treating \(abc\) as a seventh face would give \(5-9+7=3\), not \(2\). It would also count each base edge three times: for instance, \(ab\) already occurs in \(xab\) and \(yab\), and adding \(abc\) would give it a third occurrence. Both calculations contradict the requirement that an edge has exactly two local sides.
The reconstruction depends on the correct face list, not merely on a collection of cycles in the graph. For a valid list, the useful checks are complementary: each edge must appear in two facial cycles, the corners at each vertex must form a cyclic order, and the resulting counts must satisfy Euler’s formula for the sphere.
Check Your Understanding
Use the definitions and reconstruction procedure to answer the following questions.
- Why does a facial cycle contribute a pair of consecutive incident edges at each vertex it contains?
- In the triangular bipyramid, how many listed facial cycles contain edge \(xc\)? Name them.
- For a three-connected plane graph, why does the number of edge-face incidences counted from faces equal twice the number of edges?
- Explain why adding the cycle \(abc\) as a face in the triangular bipyramid gives an invalid face list.
- What information about an embedding is lost if one records only the edge set of each face boundary and omits the cyclic order of that boundary?