6 min read
On this page

Planar Graphs

A planar graph is a graph that can be drawn in the plane without any edge crossings. Planarity has deep connections to topology, graph coloring, and algorithm design.

Planar Embeddings

A planar embedding (or planar drawing) of a graph is a mapping of vertices to points and edges to curves in the plane such that edges only intersect at shared endpoints.

A graph is planar if it admits at least one planar embedding. A non-planar graph has no crossing-free drawing.

A face is a connected region of the plane bounded by edges in a planar embedding. Every planar embedding has exactly one unbounded (outer) face.

Example: K₄ (tetrahedron) is planar with 4 faces (3 triangular inner faces + 1 outer face).

Euler's Formula

For a connected planar graph with v vertices, e edges, and f faces:

v - e + f = 2

This is one of the most beautiful results in mathematics, connecting topology to combinatorics.

Example: K₄ has v = 4, e = 6, f = 4. Check: 4 - 6 + 4 = 2. ✓

Generalization: For a planar graph with c connected components:

v - e + f = 1 + c

Consequences of Euler's Formula

For simple connected planar graphs with v ≥ 3:

e ≤ 3v - 6

Proof: Each face is bounded by at least 3 edges, and each edge borders at most 2 faces. So 2e ≥ 3f, giving f ≤ 2e/3. By Euler: v - e + f = 2, so f = 2 - v + e. Then 2 - v + e ≤ 2e/3, which gives e ≤ 3v - 6. ∎

Corollary: K₅ is not planar. (v = 5, e = 10, but 3(5) - 6 = 9 < 10.)

For triangle-free planar graphs (no cycles of length 3):

e ≤ 2v - 4

Proof: Each face has at least 4 boundary edges. So 2e ≥ 4f, giving f ≤ e/2. Then e ≤ 2v - 4. ∎

Corollary: K₃,₃ is not planar. (v = 6, e = 9, bipartite so triangle-free, but 2(6) - 4 = 8 < 9.)

Minimum degree bound: Every simple planar graph has a vertex of degree ≤ 5.

Proof: If every vertex has degree ≥ 6, then 2e = Σ deg(v) ≥ 6v, so e ≥ 3v. But e ≤ 3v - 6 < 3v. Contradiction. ∎

Kuratowski's Theorem

Theorem (Kuratowski, 1930): A graph is planar if and only if it does not contain a subdivision of K₅ or K₃,₃ as a subgraph.

A subdivision of G replaces edges with paths (inserting degree-2 vertices).

K₅:  Complete graph on 5 vertices (non-planar)
K₃,₃: Complete bipartite 3+3 (non-planar)

These are the two fundamental obstructions to planarity.

Testing planarity: This can be done in O(V + E) time using algorithms by Hopcroft-Tarjan (1974) or Boyer-Myrvold (2004).

Wagner's Theorem

Theorem (Wagner, 1937): A graph is planar if and only if it does not contain K₅ or K₃,₃ as a minor.

A graph minor of G is obtained by:

  1. Deleting vertices
  2. Deleting edges
  3. Contracting edges (merging endpoints)

Wagner's theorem is equivalent to Kuratowski's but uses minors instead of subdivisions. Minors are often easier to work with theoretically.

Dual Graphs

For a connected planar graph G with a fixed embedding, the dual graph G* is:

  • One vertex in G* for each face of G.
  • An edge in G* for each edge in G, connecting the two faces that the edge separates.

Properties:

  • (G*)* = G (for connected planar graphs).
  • |V(G*)| = f(G), |E(G*)| = |E(G)|, |faces(G*)| = |V(G)|.
  • The dual of a tree is a single vertex with loops.
  • Euler's formula for G and G* are consistent.

Applications:

  • A spanning tree of G corresponds to a complementary spanning tree of G* (edges in MST of G ↔ edges not in co-tree of G*).
  • The dual of a planar graph is used in shortest path algorithms on planar graphs.
  • Map coloring is equivalent to vertex coloring the dual graph.

Graph Minor Theory

The Robertson-Seymour theorem (Graph Minor Theorem, proved over 20 papers from 1983-2004) states:

Every minor-closed family of graphs can be characterized by a finite set of forbidden minors.

A family F is minor-closed if: G ∈ F and H is a minor of G implies H ∈ F.

Examples:

  • Planar graphs: Forbidden minors = {K₅, K₃,₃} (Wagner's theorem)
  • Forests: Forbidden minor = {K₃} (a cycle)
  • Outerplanar graphs: Forbidden minors = {K₄, K₂,₃}
  • Graphs of treewidth ≤ k: Finite set of forbidden minors (but the set grows enormously)

Consequences: For any minor-closed property, there is a polynomial-time algorithm to test it (via forbidden minor testing). However, the algorithm may not be constructive — we may not know the forbidden minors explicitly.

Outerplanar Graphs

A graph is outerplanar if it can be drawn in the plane with all vertices on the boundary of the outer face.

Equivalent: Planar with no K₄ or K₂,₃ minor.

Properties:

  • Outerplanar ⟹ χ(G) ≤ 3
  • Outerplanar ⟹ treewidth ≤ 2
  • Every outerplanar graph has a vertex of degree ≤ 2

Genus and Beyond

The genus of a graph G is the minimum number of handles that must be added to a sphere to embed G without crossings.

  • Genus 0: Planar graphs (embeddable on sphere)
  • Genus 1: Embeddable on torus (e.g., K₇)
  • Higher genus: More complex surfaces

Euler's formula for genus g:

v - e + f = 2 - 2g

Heawood Conjecture (proved except for Klein bottle): The maximum chromatic number of graphs embeddable on a surface of genus g ≥ 1 is:

⌊(7 + √(1 + 48g)) / 2⌋

Crossing Number

The crossing number cr(G) is the minimum number of edge crossings in any drawing of G.

  • cr(G) = 0 iff G is planar.
  • cr(K₅) = 1, cr(K₆) = 3.
  • Computing cr(G) is NP-hard.

Crossing Lemma (Ajtai-Chvátal-Newborn-Szemerédi, 1982): If e ≥ 4v, then:

cr(G) ≥ e³ / (64v²)

This has numerous applications in combinatorial geometry.

Planarity Testing Algorithms

Boyer-Myrvold Algorithm

O(V + E) time. Based on edge addition and embedding maintenance.

Left-Right Planarity Test

Also O(V + E). Uses a characterization based on DFS and T-edges vs B-edges.

Practical Approach

For implementation, Boyer-Myrvold is well-suited. Many graph libraries include planarity testing (e.g., Boost Graph Library, NetworkX, OGDF).

Real-World Applications

  • Circuit board design (PCB): Minimizing wire crossings. Planar circuits require fewer layers.
  • VLSI layout: Planar graphs model single-layer circuit designs. Non-planar requires via holes between layers.
  • Map coloring: As discussed, planarity guarantees 4-colorability.
  • Network visualization: Planar layouts are easier to read. Graph drawing algorithms often try to minimize crossings.
  • Road networks: Road maps are approximately planar (bridges and tunnels are exceptions). This enables efficient algorithms: shortest paths in planar graphs can be computed in O(n) with preprocessing.
  • Mesh generation: Finite element methods use planar (triangulated) meshes for simulation.
  • Geographic information systems: Maps, boundaries, and spatial data are naturally planar.