planarity

Planarity is a property of a graph describing whether the graph can be drawn on the plane without any edge crossings. A drawing with no edge intersections is called a planar embedding, and the regions bounded by the edges are called faces.

Many familiar graphs are planar, including trees, cycles, and the complete graph K4. In contrast, the complete graph K5 and the complete bipartite graph K3,3 are classic examples of non-planar graphs. Planarity is preserved under taking subgraphs, so any graph containing a non-planar subgraph is non-planar.

Two fundamental characterizations govern planarity. Kuratowski’s theorem states that a finite graph is planar if and only if it contains no subdivision of K5 or K3,3. Wagner’s theorem provides an equivalent minor-based viewpoint: a graph is planar if and only if it contains no K5 or K3,3 minor. Both theorems give practical criteria for proving non-planarity.

For a connected planar graph with V vertices, E edges, and F faces, Euler’s formula holds: V − E + F = 2. This leads to useful bounds: for simple planar graphs with V ≥ 3, E ≤ 3V − 6; if the graph contains no triangles, E ≤ 2V − 4. A graph attaining E = 3V − 6 is called maximal planar (a triangulation).

Planarity testing can be done efficiently; linear-time algorithms exist to determine planarity and, when possible, produce a planar embedding. Applications include circuit layout, geographic information systems, and network visualization, where crossing-free representations are desirable. Planar graphs can also be studied on surfaces other than the plane, with the sphere providing a natural model for many embeddings.