A non-planar graph cannot be embedded in the plane without an edge intersection away from shared endpoints. This matters when drawing graphs: intersections can obscure flow, separate adjacent vertices, and make labels unreadable, so layouts aim for as few crossings as possible. section 15.1.1 section 15.3
Use these structural facts to recognize or test non-planarity:
- Kuratowski’s theorem characterizes planarity: a graph is non-planar when it contains K5, K3,3, or a subdivision of either as a subgraph. section 15.1.1
- K5 and K3,3 are the simplest non-planar graphs; removing an edge from K5 produces a graph that can be embedded without intersections. section 15.2.1
- For a simple connected graph with at least three vertices, |E| > 3|V| − 6 rules out planarity; for triangle-free graphs with more than three vertices, |E| > 2|V| − 4 does the same. section 15.2.2
- These edge-count checks run in O(V+E), but passing them does not prove planarity; general planarity testing requires a fuller algorithm. section 15.2.2
K6 layout
A naïve embedding of K6 has 15 crossing pairs of edges, while a minimum-crossing embedding has only 3 intersections. The graph remains non-planar, but layout quality improves substantially.
Planarity testing and minimum-crossing layout are different tasks. Efficient algorithms can produce planar embeddings for planar graphs, but finding the minimum crossing number for generic non-planar graphs is NP-complete; checking whether the number is exactly one is a narrower exception. section 15.3.1
