Planar Graphs and Plane Drawings

Planar graphs can be drawn in the plane without edge crossings, a property with profound implications for circuit design, geographic information systems, and computational geometry.

DefinitionPlanar Graph

A graph $G$ is planar if it can be drawn in the plane such that edges intersect only at their endpoints. Such a drawing is called a plane graph or planar embedding.

A face of a plane graph is a maximal connected region of the plane not containing any vertices or edges. One face is unbounded (the outer face).

TheoremEuler's Formula

For a connected plane graph with $n$ vertices, $m$ edges, and $f$ faces: $n - m + f = 2$

This fundamental formula holds for all plane graphs and generalizes to graphs on other surfaces (genus affects the constant).

ExampleComplete Graph $K_4$

The complete graph $K_4$ is planar: draw vertices as corners of a triangle with one vertex inside. We have $n=4$ , $m=6$ , and $f=4$ (three triangular faces plus outer face). Verify: $4 - 6 + 4 = 2$ ✓.

However, $K_5$ is non-planar: it cannot be drawn without crossings. This is a classical result proved using Euler's formula and edge/face inequalities.

DefinitionSubdivision and Homeomorphism

A subdivision of graph $G$ is obtained by replacing edges with paths (adding vertices of degree 2 on edges). Graphs $G$ and $H$ are homeomorphic if both can be obtained from the same graph by subdivisions.

Homeomorphic graphs have the same planarity: if $G$ is planar, so is any subdivision.

TheoremKuratowski's Theorem

A graph is planar if and only if it contains no subdivision of $K_5$ (complete graph on 5 vertices) or $K_{3,3}$ (complete bipartite graph) as a subgraph.

These two graphs are the minimal non-planar graphs: they are non-planar, but removing any edge makes them planar.

Remark

Wagner's Theorem provides an equivalent characterization using minors (contracting edges) instead of subdivisions: $G$ is planar if and only if it has no $K_5$ or $K_{3,3}$ minor. Graph minors form a deep theory connecting planar graphs to more general graph structure.

DefinitionPlanar Embedding Algorithms

Several $O(n)$ linear-time algorithms exist for planarity testing and embedding:

Hopcroft-Tarjan algorithm (1974): DFS-based approach
Boyer-Myrvold algorithm (2004): Simplified version, easier implementation
Left-Right algorithm: Uses PC-trees for efficiency

These algorithms not only determine planarity but construct explicit embeddings.

Planar graphs have applications in VLSI design (minimizing circuit layers), cartography (map coloring), and facility location problems. Understanding planarity is essential for computational geometry and graph drawing algorithms.