Planar Graph Checker

What Is a Planar Graph?

A planar graph is a graph that can be embedded in the Euclidean plane — that is, drawn on a flat surface so that no two edges intersect except at their shared endpoints. Equivalently, it can be drawn on the surface of a sphere without crossings. This property has profound theoretical importance and practical applications across computer science, engineering, and mathematics.

Familiar examples of planar graphs include trees (no cycles, hence always planar), polygon graphs like triangles and squares, and the skeleton of any convex polyhedron (tetrahedron, cube, dodecahedron). The complete graph K₄ and the utility graph are planar; K₅ (five cities all directly connected) is the simplest non-planar graph.

Euler's Formula: V − E + F = 2

The cornerstone of planarity theory is Euler's polyhedral formula, discovered by Leonhard Euler in 1752. For any connected planar graph with V vertices, E edges, and F faces (regions bounded by edges, including the unbounded outer face):

V − E + F = 2

The quantity χ = V − E + F is called the Euler characteristic. For connected planar graphs χ = 2; for disconnected graphs with C components, χ = C + 1. This formula immediately gives two necessary conditions for planarity:

• For any simple planar graph with V ≥ 3: E ≤ 3V − 6 (since each face is bounded by at least 3 edges)
• For bipartite planar graphs with V ≥ 3: E ≤ 2V − 4 (bipartite graphs have no odd cycles, so each face needs at least 4 boundary edges)

These are necessary but not sufficient conditions. A graph violating either bound is definitely non-planar; one satisfying both may still be non-planar (for example, the Petersen graph passes E ≤ 3V−6 but is non-planar).

Kuratowski's Theorem

Kuratowski's theorem (1930) provides the complete characterization: a finite graph is planar if and only if it contains no subdivision (also called a topological minor) of K₅ or K₃₄₃. A subdivision of a graph replaces each edge with a path of one or more edges — the internal vertices of these paths are called subdivision vertices.

K₅ is the complete graph on 5 vertices (10 edges). K₃₄₃ is the complete bipartite graph with parts of size 3 and 3 (9 edges, representing three utilities connected to three houses). These two graphs are the unique minimal non-planar graphs.

Wagner's Theorem (Graph Minors Version)

An equivalent formulation is Wagner's theorem (1937): a graph is planar if and only if it has neither K₅ nor K₃₄₃ as a graph minor. A minor is obtained by contracting edges, deleting edges, or deleting vertices — a stronger operation than subdivision. Wagner's theorem connects planarity to the deep Graph Minor Theory of Robertson and Seymour.

The Four Color Theorem

Every planar graph is 4-colorable: its vertices can be colored with at most 4 colors such that no two adjacent vertices share the same color. This is the celebrated Four Color Theorem, first conjectured in 1852 and proved in 1976 by Appel and Haken — the first major theorem proved with substantial computer assistance. In map-coloring terms: any political map can be colored with 4 colors so that no two countries sharing a border have the same color.

Graph Genus

For non-planar graphs, the genus g is the minimum number of handles attached to a sphere that allows a crossing-free embedding. Planar graphs have genus 0. K₅ and K₃₄₃ have genus 1 (they embed on a torus but not a sphere). A lower bound for non-bipartite graphs is:

g ≥ ⌈(E − 3V + 6) / 6⌉

Reference Table: Common Graphs

Applications of Planar Graphs

• Circuit board design (PCB layout): A circuit is planar if its components can be laid on a single layer without wire crossings, reducing cost and interference.
• VLSI chip design: Minimizing wire crossings in integrated circuits uses planarity testing algorithms (linear-time algorithms due to Hopcroft-Tarjan, 1974).
• Map coloring: Political maps are planar graphs; the four color theorem guarantees 4-color solutions.
• Network layout: Visualizing planar networks (water mains, electrical grids, subway maps) without visual clutter exploits planarity.
• Computer graphics: Planar mesh triangulations underlie 3D rendering algorithms and finite-element simulations.
• Molecular chemistry: Some molecular graphs (like glucose rings) are planar; non-planar molecular graphs correspond to topologically linked or knotted molecules.