Chapter 37. Plane Embeddings

A plane embedding is a crossing-free placement of a graph in the plane. It gives a planar graph a particular geometric form. The graph itself records which vertices are adjacent. The embedding records how those adjacencies are arranged around each vertex and how the drawing divides the plane into faces.

A planar graph may have many different plane embeddings. Some embeddings have different outer faces. Some place cycles inside other cycles. Some give different cyclic orders of incident edges around a vertex. These differences affect faces, dual graphs, graph drawing, and planar algorithms.

37.1 Drawings and Embeddings

Let $G = (V,E)$ be a graph. A drawing of $G$ in the plane assigns:

A drawing is an embedding when distinct edges intersect only at common endpoints. Thus an embedding is a drawing without improper crossings. This is the standard strict meaning of graph embedding in topological graph theory.

A graph is planar if it admits at least one plane embedding. A plane graph is a planar graph together with a chosen embedding.

The difference is small in language but large in use. A planar graph is an abstract object. A plane graph is an embedded object.

37.2 The Role of the Outer Face

Every plane embedding divides the plane into regions called faces. Exactly one face is unbounded. This face is called the outer face.

The choice of outer face is part of the embedding in the plane. If the same graph is drawn on the sphere instead, no face is distinguished as outer. This is one reason planar graph theory often treats plane drawings and spherical drawings as essentially equivalent, with the outer face arising only after choosing a projection to the plane.

For example, a cycle $C_n$ has two faces in any plane embedding: an inside face and an outside face. Either face may be treated as the outer face after redrawing the graph.

37.3 Rotation Around a Vertex

A plane embedding determines a cyclic order of the edges incident to each vertex. This cyclic order is called the rotation at the vertex.

Suppose a vertex $v$ is incident with four edges

In a drawing, these edges occur around $v$ in some circular order, such as

Only the cyclic order matters. Thus

and

describe the same rotation.

The collection of all vertex rotations is called a rotation system. An embedded graph determines such a system, and rotation systems give a combinatorial way to encode embeddings.

37.4 Combinatorial Embeddings

A topological embedding uses points and curves. A combinatorial embedding records the same incidence information by cyclic orders.

For many purposes, the exact shape of an edge is irrelevant. A curved edge and a straight edge represent the same embedded structure if they preserve the same vertex-edge incidences and the same local order around vertices.

A combinatorial embedding is therefore a discrete description of a plane embedding. It records enough information to recover the facial structure of a connected plane graph.

This point is important in algorithms. A computer usually does not store a drawing as continuous curves. It stores adjacency lists ordered according to the embedding.

37.5 Facial Walks

The boundary of a face is followed by a closed walk in the graph. This walk is called a facial walk. The length of the facial walk is the size of the face.

For a simple cycle embedded as a polygon, the bounded face has facial walk

The outer face has the same boundary in the reverse direction.

In more complicated plane graphs, a vertex or edge may appear more than once in the boundary walk of a face. This happens, for example, in trees. A tree has only one face, and each edge is encountered twice when tracing the boundary of that face. Lecture notes commonly define faces as the connected regions separated by the drawing, and facial walks as the closed walks forming their boundaries.

37.6 Bridges and Face Boundaries

A bridge is an edge whose deletion increases the number of connected components. In a plane embedding, a bridge lies on the boundary of the same face on both sides.

This explains why an edge may appear twice in a facial walk. If an edge is not a bridge, it usually separates two distinct faces. If an edge is a bridge, both sides of the edge belong to the same face.

For example, in a tree with $n$ vertices, there are

edges and only one face. Euler’s formula gives

The single face has boundary length $2e$, because every edge is traversed once in each direction.

37.7 Equivalent Embeddings

Two plane embeddings are considered equivalent when one can be continuously deformed into the other without changing incidences or creating crossings.

This means the exact metric data do not matter. Edge lengths, angles, and curvature are ignored. The embedding preserves the topological arrangement of the graph.

For connected plane graphs, the rotation system usually captures this arrangement up to orientation. Reversing the orientation of the whole plane reverses every cyclic order, but it does not change the underlying planar structure.

37.8 Straight-Line Embeddings

A plane embedding may use curved edges. A stronger kind of drawing uses straight-line segments for all edges.

A fundamental theorem of planar graph drawing, often called Fary’s theorem, states that every simple planar graph has a straight-line plane drawing. Thus, for simple planar graphs, allowing curved edges does not enlarge the class of planar graphs. The curves may be replaced by line segments while keeping the drawing crossing-free.

This theorem justifies many geometric pictures of planar graphs. It also supports applications in graph drawing, mesh generation, and computational geometry.

37.9 Plane Embeddings and Algorithms

Many planar graph algorithms assume that an embedding is already available. The embedding gives more information than the abstract adjacency relation.

For example, an embedding supports:

Without an embedding, an algorithm may first need to test planarity and construct one. With an embedding, the algorithm can work directly with faces and boundary walks.

37.10 Example: Two Embeddings of the Same Graph

Consider a graph formed by a square with one diagonal. Let the vertices be

around the square, and let the diagonal be $13$.

One embedding has the square boundary

with diagonal $13$ inside. The bounded faces are triangles

and

The outer face is

A different drawing may place another face outside. The abstract graph has the same vertices and edges, but the selected outer face changes the plane embedding.

37.11 Plane Embeddings and Duality

The dual graph of a connected plane graph depends on the embedding. It has one vertex for each face of the original embedding. Two dual vertices are adjacent when their corresponding faces share an edge.

Because the faces depend on the embedding, the dual graph also depends on the embedding. The same planar graph may have nonidentical duals under different embeddings.

This is one reason plane embeddings are treated as mathematical objects, not merely illustrations.

37.12 Summary

A plane embedding is a crossing-free drawing of a graph in the plane. It turns a planar graph into a plane graph by fixing the arrangement of edges around vertices and the resulting faces.

The main data of an embedding are:

Plane embeddings form the bridge between abstract graph theory and planar geometry. They make it possible to speak precisely about faces, dual graphs, map coloring, planar drawing, and algorithms that exploit planar structure.