nonplanarity

Nonplanarity is a property in graph theory describing the impossibility of drawing a graph on the plane without edge crossings. A graph is planar if such a drawing exists; if no crossing-free embedding exists, the graph is nonplanar. The subject centers on how a graph can be represented in the plane and how structural constraints prevent a crossing-free drawing.

Two classical minimal nonplanar graphs are the complete graph on five vertices, K5, and the complete bipartite graph K3,3. A central result, Kuratowski's theorem, characterizes nonplanarity: a finite graph is nonplanar if and only if it contains a subdivision of K5 or K3,3 as a subgraph. An alternative, often cited, formulation is Wagner's theorem: a graph is planar if and only if it has neither K5 nor K3,3 as a minor. These results show that nonplanarity is witnessed by relatively small, well-understood configurations.

In practice, to prove nonplanarity one can exhibit a subdivision of K5 or K3,3 within the graph or identify a K5 or K3,3 minor. Planarity testing algorithms determine whether a given graph is planar; notable is a linear-time algorithm by Hopcroft and Tarjan. The concept extends to higher-genus surfaces: a nonplanar graph may embed without crossings on a torus or other surfaces, but not on the plane.

Nonplanarity has implications for graph drawing, network design, and circuit layout, where crossing edges can be undesirable or costly. It also underpins theoretical results about graph structure, minors, and embeddings, reflecting how local constraints influence global representations.