Planar graph

A planar graph admits at least one graph drawing in which edges meet only at common endpoints. This is a property of the abstract graph, not a requirement on every graph drawing. A plane graph specifies one such drawing.^[ref]

For example, the complete graph $K_4$ joins every pair of four vertices, giving six edges. Put its vertices at the corners of a square and its diagonals cross. Instead put $A,B,C$ at the corners of a triangle and $D$ inside it: the same six edges $AB,AC,BC,AD,BD,CD$ now meet only at their endpoints. The first graph drawing obscures planarity; the second proves it. In particular, its crossing number is zero.

The distinction matters whenever connections must fit on one surface without intersecting. A failed graph drawing may only need rearrangement, whereas nonplanarity by edge counts proves that every rearrangement fails.

A finite simple graph is a planar graph if and only if it contains no graph subdivision of the complete graph $K_5$ or the complete bipartite graph $K_{3,3}$ as a subgraph; equivalently, neither is a topological minor. The easy direction follows by tracing each replacement graph path as one drawn edge. The converse asserts that every failure of planarity contains one of these two patterns.^[ref]

Graph Theory by Reinhard Diestel (Planar Graphs preview, §4.4, Theorem 4.4.6, printed p. 111) dates Kuratowski's theorem to 1930 and the equivalent graph minor characterization to 1937. These dates are that textbook's historical attribution.

A plane graph is a planar graph with a specified graph drawing whose edges meet only at common endpoints, also called an embedding in the Euclidean plane. Its faces of a plane graph and facial boundary walks refer to that embedding. This geometric use of embedding differs from a graph embedding, which maps one abstract graph into another.

A face of a plane graph is a connected component of the Euclidean plane after removing the drawn vertices and edges. Count the outer face too. This is the plane counterpart of a face of a planar map on the sphere.^[ref]

The outer face is the unique unbounded face of a plane graph for a finite plane graph. It counts once even though it surrounds the whole graph drawing. A tree has only this face of a plane graph.

For a finite connected graph embedded as a plane graph, follow the edges around a face of a plane graph to obtain a closed walk. Count traversals, not distinct edges: a bridge in a graph occurs twice along one facial boundary walk. Each edge contributes two sides in total.^[ref]

For the three-vertex graph path $A-B-C$, the only facial boundary walk is $A,B,C,B,A$, of length four. Both edges are bridges in a graph; neither is a graph cycle. Thus a facial boundary walk need not be a graph cycle.

The honeycomb lattice is the periodic degree-three planar graph consisting of the vertices and edges of a regular hexagonal tiling. It has two vertex classes; every edge joins opposite classes. Its planar dual graph is the triangular lattice.

The martini lattice is obtained from the honeycomb lattice by replacing every vertex in one of its two vertex classes by a triangle, attaching its three former incident bonds to the triangle's three vertices. It is a periodic degree-three planar graph, with triangular faces and nine-sided faces. Each decorated vertex and its incident bonds is a three-terminal cell with three internal triangle bonds and three terminal spokes. Its independent bond percolation threshold is $1/\sqrt{2}$, as follows from three-terminal cell partition duality.

Every finite planar graph has chromatic number at most four. This stronger theorem is distinct from the elementary five colour theorem; the latter's Kempe chain proof does not prove this assertion.

Every finite planar graph admits a proper vertex coloring with at most five colors. Euler formula for a connected planar graph supplies a vertex of degree at most five. Inductively color its deletion. The only obstruction is five differently colored neighbours in cyclic order. If opposite neighbours 1 and 3 are in different two-color components, interchange one component. If they are connected, planarity prevents opposite neighbours 2 and 4 from being connected in their two-color subgraph, and that interchange frees a color instead. This is a Kempe chain proof.

A planar map is a planar graph together with a fixed embedding in the sphere, considered up to orientation-preserving homeomorphism. A rooted planar map has a distinguished oriented edge, which removes most embedding symmetries.

A face of a planar map is a connected component of the complement of its embedded graph. Its degree is the number of edge incidences around its boundary, counted with multiplicity, and the sum of all face degrees is twice the number of edges.

A rooted planar map is a planar map with a distinguished oriented edge called its root edge. Its tail is the root vertex, and the face on a chosen side of the edge may be designated as the root face.

A planar quadrangulation is a planar map in which every face has degree four, with incidences counted with multiplicity. A pointed quadrangulation additionally has a distinguished vertex.

A squaregraph has separate conditions on bounded faces and interior vertex degrees; its outer face need not be quadrilateral.

The trivial bijection sends a rooted planar map with $n$ edges to a rooted planar quadrangulation with $n$ faces. Put one new vertex in each face and, in each corner, connect that face vertex to the incident original vertex. Each original edge then lies inside one quadrangular face; deleting the original edges gives the quadrangulation. The face bipartition recovers the original vertices and hence the inverse map.

A planar dual graph has one vertex in each face of a fixed planar embedding and one dual edge crossing each primal edge.

This is the planar-embedding case of a dual graph.

For a fixed finite plane graph, the complementary dual configuration opens a dual edge exactly when its primal edge is closed. Its components correspond to faces of the spanning open primal graph. The componentwise Euler formula for a connected planar graph gives the displayed identity. The outer face and isolated primal vertices are included; the identity also handles disconnected graphs, bridges and loops.

In planar bond percolation, declare a dual edge open exactly when the primal edge it crosses is closed. Independent primal parameter $p$ then gives independent dual parameter $1-p$.

A planar finite network with three boundary terminals induces one of five connection partitions: all three connected, all three separate, or one connected pair and an isolated third terminal. Put three dual terminals on the intervening boundary arcs. Passing to the planar dual graph interchanges the all-connected and all-separate partitions and permutes the three pair partitions. If the network is symmetric under all terminal permutations, equality $P_3=P_0$ of the first two probabilities makes its whole partition law dual-invariant. Independent cells on a self-dual triangular terminal arrangement then give identical primal and dual coarse connection laws. Infinite connectivity is preserved because cells are uniformly finite. For a martini lattice cell with six independent bonds of common parameter $p$, $P_3=3p^5-2p^6$ and $P_3-P_0=(2p^2-1)(p^4-3p^3+2p^2+1)$. The unique zero in $[0,1]$ is $1/\sqrt{2}$.

In bond percolation on the square lattice, the outer boundary of a finite percolation cluster, after filling its holes, consists of closed bonds. Their crossing edges in the planar dual graph form a connected enclosing contour, and hence belong to a single dual bond percolation cluster $K$. If $|K|=m$, both its coordinate widths are at most $m-1$, so the enclosed primal cluster contains at most $m^2$ vertices. A contour enclosing the origin also places every vertex of $K$ within distance $m+1$ of the origin. An exponential volume tail for the subcritical dual bond percolation clusters thus gives a bound $C{e}^{-c\sqrt{n}}$ for a finite primal cluster of size at least $n$.

For a rectangle in a planar lattice, exactly one of an open primal left-to-right crossing and a closed dual top-to-bottom crossing occurs.

For the lattice rectangle with graph vertices $\{0,\dots ,n\}\times \{0,\dots ,n-1\}$, let $H_n$ be an open left-to-right crossing. Its complementary event is a closed dual top-to-bottom crossing. The dual crossing rectangle has width $n-1$ and height $n$, so rotation and translation identify it with the original rectangle. Boundary edges along the starting and ending sides do not affect the crossing event. At $p=1/2$ the primal and dual edge states have identical laws, henceThe one-unit adjustment in the side lengths makes the symmetry exact rather than an informal assertion about a finite graph vertex square.

For a finite connected graph with at least one vertex, embedded as a plane graph, let $n$ count vertices, $m$ count edges, and $f$ count faces of a plane graph, including the outer face. ThenThe hypotheses refer to an actual embedding; regions in a crossing-filled graph drawing do not supply its $f$.^[ref]

In the plane graph $K_4$ pictured above, three bounded faces of a plane graph and the outer face give $4-6+4=2$. A square cycle graph gives $4-4+2=2$, while the graph path $A-B-C$ gives $3-2+1=2$. Changing a crossing into a new vertex changes the graph: the square-and-diagonals drawing then has five vertices, eight edges, and five faces of a plane graph, giving $5-8+5=2$.

A proof outline deletes edges on graph cycles. Each deletion preserves the connected graph and merges two faces of a plane graph, leaving $n-m+f$ unchanged. Eventually a tree remains, with $m=n-1$ and $f=1$. Adding the point at infinity identifies the plane picture with a sphere; the value two agrees with its Euler characteristic and the cell-count formula for Euler characteristic.

For a connected cellular spherical planar graph with vertex degrees at least three and face sizes at least three, degree/face double counting and the Euler formula for a connected planar graph give ${\sum }_n(6-n)F_n=12+{\sum }_m(2m-6)V_m\ge 12$. The left side is at most $3(F_3+F_4+F_5)$, proving the displayed bound. In particular a convex polyhedron has at least four faces of size at most five.

A finite simple graph that is a connected graph and a planar graph, with $n\ge 3$ vertices and $m$ edges, satisfies $m\le 3n-6$. Choose a plane graph: each facial boundary walk has length at least three, so $3f\le 2m$. Substitute $f=2-n+m$ from the Euler formula for a connected planar graph.^[ref]

The complete graph $K_4$ attains equality: $6=3\cdot 4-6$. The bound also holds for a disconnected finite simple graph that is a planar graph with $n\ge 3$: place its connected components of a graph in disjoint regions and join them with new bridges in a graph, then apply the connected bound.

If a finite simple graph is a connected graph, a bipartite graph, and a planar graph, with $n\ge 3$ vertices, then $m\le 2n-4$. Every facial boundary walk has even length and length at least three, hence at least four. Thus $4f\le 2m$; substitute the Euler formula for a connected planar graph.^[ref]

The square cycle graph attains equality: $4=2\cdot 4-4$. The three-vertex graph path also attains equality: $2=2\cdot 3-4$. Its repeated bridges in a graph illustrate why counting facial boundary walk length correctly matters. Neither bound applies unchanged to a multigraph: two vertices may support arbitrarily many parallel edges in a plane graph.

The complete graph $K_5$ has $n=5$ and $m=\left(\genfrac{}{}{0ex}{}{5}{2}\right)=10$, exceeding the planar graph edge bound $3\cdot 5-6=9$. Therefore it is not a planar graph. The complete bipartite graph $K_{3,3}$ has $n=6$ and $m=3\cdot 3=9$. The general bound allows twelve edges, but the bipartite planar graph edge bound allows only eight, proving nonplanarity.

These are necessary bounds, not a complete planarity test. For an original counterexample, subdivide every edge of $K_{3,3}$ once. The resulting simple graph is a connected graph with $n=15$, $m=18$, and is bipartite: put all original vertices in one part and all nine new vertices in the other. Both inequalities hold, $18\le 39$ and $18\le 26$. Nevertheless, a crossing-free graph drawing would let us trace each two-edge graph path as one curve, producing an impossible embedding of $K_{3,3}$. The graph subdivision preserves this obstruction. Kuratowski's theorem supplies a stronger characterization than these counts.

If every face of a connected planar graph has size at least $g>2$, double-counting edge-face incidences and using Euler's formula gives

Let a connected bridgeless planar graph have $n\ge 4$ vertices, $e$ edges, no four-cycle, and $t$ triangular faces. If no edge borders two triangular faces, thenso $f\le 8e/15$. The Euler formula for a connected planar graph then gives

The icosidodecahedral graph is the skeleton of the icosidodecahedron. It has 30 vertices, 60 edges, 20 triangular faces, and 12 pentagonal faces. Every edge separates a triangle from a pentagon, so it attains equality in the triangle-pentagon planar edge bound.