Planar Graph

This article introduces (planar) graphs and related concepts.

Planar Graphs

If a graph $G$ can be drawn on a plane $S$ such that no edges intersect except at vertices, then $G$ is said to be embeddable in plane $S$, and $G$ is called a planar graph. The drawing without intersecting edges is called a planar representation or planar embedding of $G$. This planar embedding of a planar graph is also referred to as a plane graph.

「Planar Graph」

In different Chinese texts, the meaning of "planar graph" may vary. Under the definitions in this article, a planar graph is a graph-theoretic object that may be embedded in the plane in different ways; a plane graph is a geometric object that, in addition to the graph structure, also specifies a drawing of the graph. The same planar graph often corresponds to multiple plane graphs. Therefore, if a conclusion in this article depends only on the graph structure, the term "planar graph" will be used; if it also depends on the planar embedding, the term "plane graph" will be used.

The following are simple examples of plane graphs:

(Left: Butterfly graph; Right: Complete graph $K_4$ of order $4$)

The following are simple examples of non-planar graphs:

(Left: Complete graph $K_5$ of order $5$; Right: Complete bipartite graph $K_{3,3}$ with each part having $3$ vertices)

Properties

This section introduces properties of plane graphs.

Faces and Their Degrees

Let $G$ be a plane graph. The plane containing $G$ is divided by the edges of $G$ into several regions, each called a face of $G$. Among them, the unbounded face is called the unbounded face or external face, and the bounded ones are called bounded faces or internal faces. Every plane graph has exactly one external face.

The closed walk formed by all edges surrounding a face is called the boundary of that face, and the edges in the boundary are said to be incident to the face. The length of the boundary is called the degree of the face. When calculating the degree of a face, each cut edge is counted twice. The sum of the degrees of all faces in a plane graph equals twice the number of edges $|E|$.

In a plane graph, a face of degree $1$ corresponds to a loop in the graph, and a face of degree $2$ usually corresponds to a pair of parallel edges[^face-2]. In a simple connected plane graph with $|V|\ge 3$ vertices, all faces have degree at least $3$.

Euler's Formula

An important property of plane graphs is Euler's formula. It relates the number of vertices $|V|$, edges $|E|$, and faces $|F|$ of a graph.

Euler's Formula

For a connected plane graph $G$, we have

\[ |V| - |E| + |F| = 2. \]

Proof

Use mathematical induction on the number of faces $|F|$. The base case is $|F|=1$. In this case, the plane graph has exactly one external face, and all edges are cut edges. Thus, $G$ is a tree, and we must have $|E|=|V|-1$. Substituting into Euler's formula shows it holds. Assume Euler's formula holds for plane graphs with $|F| = k$ faces. For a plane graph $G$ with $|F|=k + 1$ faces, there must exist a non-cut edge $e$ that is a common edge of two distinct faces. Remove edge $e$ to obtain graph $G-e$, which has $|V|$ vertices, $|E|-1$ edges, and $|F|-1$ faces. By the induction hypothesis, Euler's formula holds for $G-e$, i.e., $|V|-(|E|-1)+(|F|-1)=2$. Rearranging gives Euler's formula for $G$. Therefore, by mathematical induction, Euler's formula holds for all plane graphs.

Corollary

For a plane graph $G$ with $k$ connected components, we have

\[ |V| - |E| + |F| = k + 1. \]

Proof

Each connected component of $G$ is a plane graph, but they share the same external face. Applying Euler's formula to each component and summing, the total vertex and edge counts are correct, but the total face count is overcounted by $(k-1)$ because the unique external face is counted $k$ times. Taking this correction into account yields $|V|-|E|+|F| = 2k - (k-1) = k+1$.

From this, we can derive relationships between the numbers of edges and vertices in a plane graph.

Theorem

For a plane graph $G$ with $k$ connected components, if every face of $G$ has degree at least $l \ge 3$, then

\[ |E| \le \dfrac{l}{l-2}(|V|-k-1). \]

Proof

Since each face of $G$ has degree at least $l$, the sum of the degrees of all faces is at least $l|F|$, i.e., $2|E| \ge l|F|$. Substituting into the corollary of Euler's formula $|V| - |E| + |F| = k + 1$, we get

\[ 2|E| \ge l(k + 1 - |V| + |E|). \]

Solving for $|E|$ using $l \ge 2$ yields

\[ |E| \le \dfrac{l}{l-2}(|V|-k-1). \]

Corollary

Let $G$ be a simple planar graph with $|V|\ge 3$. Then,

\[ |E| \le 3|V|-6. \]

Proof

When $G$ is connected, all faces have degree at least $3$. In the above theorem, set $k=1$ and $l=3$ to obtain $|E|\le 3|V|-6$.

When $G$ is disconnected, consider two cases:

If there exists a connected component with at least $3$ vertices, then for each such component we have $|E_i|\le 3|V_i|-6$. For components with fewer than $3$ vertices, we have $|E_i|\le |V_i| \le 3|V_i|$. Summing the inequalities for all components gives $|E|\le 3|V|-6$.
If all components have fewer than $3$ vertices, then overall $|E|\le |V|$. Since $|V|\ge 3$ implies $|V|\le 3|V|-6$, we still have $|E|\le 3|V|-6$.

Thus, the proposition holds.

This corollary shows that simple planar graphs are sparse.

Dual Graph

Every plane graph has a corresponding (geometric) dual graph.

Let $G$ be a plane graph. Construct a graph $G^*$ as follows:

Inside each face $f_i$ of $G$, draw a vertex $v_i^*$.
For each edge $e$ of $G$, if $e$ lies on the common boundary of faces $f_i$ and $f_j$, draw an edge $e^*$ connecting $v_i^*$ and $v_j^*$ that crosses $e$ exactly once and does not intersect any other edges of $G$ or $G^*$. In particular, if $e$ appears only on the boundary of a single face $f_i$, draw a loop incident to $v_i^*$ that crosses $e$.

The resulting graph $G^*$ is called the dual graph of $G$.

Theorem

Let $G^*$ be the dual graph of plane graph $G$. Then, $G^*$ is a connected plane graph. Moreover, $G^{**}$ is isomorphic to $G$ if and only if $G$ is connected.

Proof

That $G^*$ is a plane graph is guaranteed by its construction. We also need to show $G^*$ is connected. For any two vertices $v^*_i,v^*_j$ in $G^*$, consider a straight line segment in the plane connecting $v^*_i$ and $v^*_j$. Suppose it passes through faces and edges of $G$ in sequence: $f_i,e_{s_1},f_{s_1},\cdots,f_{s_{r-1}},e_{s_r},f_j$, corresponding to vertices and edges $v_i^*,e_{s_1}^*,v^*_{s_1},\cdots,v^*_{s_{r-1}},e^*_{s_r},v^*_j$ in $G^*$. By construction of $G^*$, adjacent vertices and edges in this sequence are incident, so this describes a walk in $G^*$. Hence, $G^*$ is connected.

$G^{**}$ is the dual graph of $G^*$ and is necessarily connected. Thus, for $G$ to be isomorphic to $G^{**}$, it is necessary that $G$ be connected. Next, we show this condition is also sufficient. To do so, it suffices to show that when $G$ is connected, $G$ satisfies the construction requirements for being the dual graph of $G^*$. Since edges of $G^*$ naturally correspond to edges of $G$, we only need to show that each face of $G^*$ contains exactly one vertex of $G$. For any face $f^*$ of $G^*$, let $e^*$ be an edge on its boundary. Then, one endpoint of the corresponding edge $e$ in $G$ must lie inside $f^*$; thus, $f^*$ contains at least one vertex of $G$. Since both $G$ and $G^*$ are connected, Euler's formula holds; and since $G$ and $G^*$ have the same number of edges, and the number of faces of $G$ equals the number of vertices of $G^*$, the number of vertices of $G$ equals the number of faces of $G^*$. Therefore, each face of $G^*$ contains exactly one vertex of $G$. The proposition holds.

There are many correspondences between the structure of a plane graph and its dual:

Faces in $G$ correspond to vertices in $G^*$, edges in $G$ correspond to edges in $G^*$, and vertices in $G$ correspond to faces in $G^*$.
Loops in $G$ correspond to cut edges in $G^*$, and loops in $G^*$ correspond to cut edges in $G$.
Edge cuts in $G$ correspond to cycles in $G^*$, and cycles in $G^*$ correspond to edge cuts in $G$.

Note that the concept of a dual graph is defined only for a specific plane graph, not for an arbitrary planar graph. In fact, the dual graphs of two isomorphic plane graphs may not be isomorphic. That is, different planar embeddings of the same graph may have non-isomorphic dual graphs.

Example

The figure below shows two isomorphic plane graphs whose dual graphs are not isomorphic.

The reason the dual graphs are not isomorphic is that the right graph has a face of degree $1$, so its dual graph has a vertex of degree $1$, while the left graph does not.

Transforming problems on plane graphs to their dual graphs can sometimes make them easier to solve. A classic example is that the minimum cut problem in a plane graph can be transformed into a shortest path problem in its dual graph. Let $G$ be a plane graph with edge weights, and let $s,t$ be two vertices. We want to find the minimum $s$-$t$ cut.

As shown, by choosing an appropriate planar embedding, we can always ensure that $s$ and $t$ lie on the boundary of the external face of $G$. Additionally, add rays extending from $s$ and $t$ to split the external face into two parts $f_{+}$ and $f_{-}$. Based on this embedding, construct the dual graph and assign edge weights to the corresponding edges in the dual. Then, a path (thick red line) between the vertices corresponding to faces $f_{+}$ and $f_{-}$ in the dual graph $G^*$ corresponds one-to-one with an $s$-$t$ cut (thick black line) in $G$, and their weights are equal. Thus, finding the shortest path in the dual graph yields the minimum $s$-$t$ cut in the original graph.

More Results

Of course, there are many famous results about planar graphs. This section briefly lists them without detailed discussion.

Four Color Theorem

(Loopless) planar graphs are $4$‑colorable.

Fáry's Theorem

Every simple planar graph has a planar embedding in which all edges are straight line segments.

Theorem (Wood)

A planar graph has at most $8|V|-16$ maximal cliques.

Theorem (Tutte)

Every $4$‑connected planar graph is Hamiltonian.

Planarity Testing

This section discusses methods to determine whether a given graph is planar.

Forbidden Graphs

The most classic characterization of planar graphs uses forbidden graphs.

First, $K_5$ and $K_{3,3}$ are not planar.

Theorem

$K_5$ and $K_{3,3}$ are not planar.

Proof

As mentioned earlier, a simple connected plane graph with $|V|\ge 3$ must satisfy

\[ |E| \le \dfrac{l}{l-2}(|V|-2). \]

where $l$ is the minimum face degree. For $K_5$, $l=3,~|V|=5,~|E|=10$, so $K_5$ cannot be drawn as a plane graph. For $K_{3,3}$, $l=4,~|V|=6,~|E|=9$, so $K_{3,3}$ cannot be drawn as a plane graph.

In fact, they are the minimal structures that make a graph non-planar. That is, if a graph does not contain (in some way) these two graphs as substructures, then it must be planar.

The first planarity criterion is Kuratowski's theorem. It uses the concept of graph homeomorphism: two graphs $G_1$ and $G_2$ are homeomorphic if they are isomorphic or become isomorphic after repeatedly inserting or removing vertices of degree $2$. The result is as follows:

Kuratowski's Theorem

A graph $G$ is planar if and only if $G$ contains no subgraph homeomorphic to $K_5$ or $K_{3,3}$.

Another related theorem is Wagner's theorem. It characterizes planar graphs using edge contraction. Contraction means repeatedly contracting an edge to a point. The result is as follows:

Wagner's Theorem

A graph $G$ is planar if and only if $G$ has no subgraph that can be contracted to $K_5$ or $K_{3,3}$.

It is relatively obvious that planar graphs do not contain such subgraphs, so the key parts of these theorems are the sufficiency of the forbidden graph conditions. Since a subgraph homeomorphic to $K_5$ or $K_{3,3}$ can always be contracted to them, but the converse is not necessarily true, Kuratowski's theorem provides a weaker and easier-to-check condition for planarity.

Planarity Testing Algorithms

Although it may not seem easy, the planarity testing problem actually has many linear-time algorithms. However, due to their typically complex implementations, they rarely appear in programming contests.

The earliest linear algorithm is the Hopcroft–Tarjan algorithm[^ht74], but its implementation is quite complex. The de Fraysseix–Ossona de Mendez–Rosenstiehl algorithm (also known as the LR planarity algorithm)[^dor06][df08][^bra09] further improves the Hopcroft–Tarjan process and is one of the best planarity testing algorithms. It is implemented in Python's NetworkX library.

Another excellent algorithm is the Boyer–Myrvold algorithm[^bm99][bm04]. It can determine in linear time whether a given graph is planar. Moreover, if the graph is planar, the algorithm outputs a planar embedding; otherwise, it outputs a Kuratowski subgraph (i.e., a subgraph homeomorphic to $K_5$ or $K_{3,3}$). It is implemented in C++'s Boost library.

More related algorithms can be found in the references at the end.

Special Planar Graphs

This section introduces several special classes of planar graphs.

Maximal Planar Graphs

For a simple planar graph $G$, if adding any edge between non-adjacent vertices results in a non-planar graph, then $G$ is called a maximal planar graph. A planar embedding of a maximal planar graph is called a maximal plane graph.

Theorem

A maximal planar graph $G$ must be connected. Moreover, when $|V|\ge 3$, $G$ has no cut edges.

Proof

If a planar graph $G$ is disconnected, then for any planar embedding, we can choose two vertices from different components and connect them inside the external face. The resulting graph is clearly still planar, contradicting the maximality of $G$. Thus, a maximal planar graph must be connected.

If a planar graph $G$ has $|V|\ge 3$ and has a cut edge $e=(u,v)$, then after removing $e$, $G - e$ has exactly two components, with $u$ and $v$ in different components. Suppose the component containing $v$ has at least two vertices. Then, we can first draw the component $G_1$ containing $u$ in the plane, choose any face $f$ of $G_1$ whose boundary contains $u$, and draw the other component $G_2$ inside $f$. Since $G_2$ is simple, the boundary of its external face is not a loop, so there must be another vertex $w\neq u,v$. Connecting $v$ and $w$ to $u$ yields a planar graph containing $G$ as a subgraph. Thus, $G$ is not maximal. Therefore, a maximal planar graph with $|V|\ge 3$ has no cut edges.

The structure of maximal plane graphs can be described more precisely.

Theorem

For a plane graph $G$ with $|V|\ge 3$, it is a maximal plane graph if and only if it is simple and every face has degree $3$.

Proof

The sufficiency is obvious. We only need to prove necessity: for a maximal plane graph $G$ with $|V|\ge 3$, every face has degree $3$. Since $G$ is a connected simple plane graph with $|V|\ge 3$, all faces have degree at least $3$. Suppose the proposition is false; then there exists a face $f$ whose boundary length is at least $4$. Since $G$ has no cut edges, this boundary must be a cycle. Let the cycle be $v_1v_2v_3v_4\cdots v_1$. If $v_1$ and $v_3$ are not adjacent, then connecting $v_1$ and $v_3$ inside $f$ would not destroy planarity, contradicting the maximality of $G$. Thus, $v_1$ and $v_3$ are adjacent; similarly, $v_2$ and $v_4$ are adjacent. However, edges $(v_1,v_3)$ and $(v_2,v_4)$ cannot lie inside $f$. This means both edges must lie outside $f$. But this is impossible: however they are drawn, these two edges must intersect. Therefore, $G$ has no face of degree greater than $3$. The proposition holds.

Corollary

For a maximal plane graph $G$ with $|V|\ge 3$, we have:

$|E|=3|V|-6$.
$|F|=2|V|-4$.

Since every face in a maximal plane graph is bounded by three edges, maximal plane graphs are also called plane triangulations.

Outerplanar Graphs

Let $G$ be a planar graph. If $G$ has a planar embedding $\tilde{G}$ such that all vertices of $G$ lie on the boundary of a single face of $\tilde{G}$, then $G$ is called an outerplanar graph. This embedding is also called an outerplanar embedding or outerplane graph. Usually, the face whose boundary contains all vertices is drawn as the external face.

Outerplanar graphs are always planar, but the converse is not necessarily true. Outerplanar graphs can also be characterized using forbidden graphs.

Theorem

A graph $G$ is outerplanar if and only if $G$ contains no subgraph homeomorphic to $K_4$ or $K_{2,3}$.

For outerplanar graphs, we can also discuss the concept of maximal outerplanar graphs. For a simple outerplanar graph $G$, if adding any edge between non-adjacent vertices results in a non-outerplanar graph, then $G$ is called a maximal outerplanar graph. An outerplanar embedding of a maximal outerplanar graph is called a maximal outerplane graph. Maximal outerplane graphs are essentially triangulations of a polygon in the plane.

Theorem

For a maximal outerplane graph $G$ with $|V|\ge 3$, where all vertices lie on the boundary of the external face, $G$ has exactly $|V|-2$ internal faces.

Proof

Use induction on $|V|$. The base case is $|V|=3$. Then $G$ is a triangle with exactly $1$ internal face, so the proposition holds. Assume the proposition holds for $|V| = k$. We prove it for $|V| = k+1$.

First, $G$ must have a vertex of degree $2$. Otherwise, every vertex (except adjacent ones on the external boundary) would need to be connected to a third vertex. Label the vertices on the external boundary consecutively, and for each $i = 1,2,\cdots,k+1$, define $f(i

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用