Planar graph Created 2026-09-24 Updated 2026-10-14
A planar graph admits at least one graph drawing in which edges meet only at common endpoints. This is a property of the abstract graph, not a requirement on every graph drawing. A plane graph specifies one such drawing.[ref]
Planar Graphs; Bipartite Matching by Albert R. Meyer (6.042J lecture 5f). Planar Graphs; Bipartite Matching, slides lec 5f.3 and 5f.12
For example, the complete graph joins every pair of four vertices, giving six edges. Put its vertices at the corners of a square and its diagonals cross. Instead put at the corners of a triangle and inside it: the same six edges now meet only at their endpoints. The first graph drawing obscures planarity; the second proves it. In particular, its crossing number is zero.
The distinction matters whenever connections must fit on one surface without intersecting. A failed graph drawing may only need rearrangement, whereas nonplanarity by edge counts proves that every rearrangement fails.
