= Planar graph
{wiki}
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.<Planar Graphs; Bipartite Matching by Albert R. Meyer (6.042J lecture 5f)>[Planar Graphs; Bipartite Matching, slides lec 5f.3 and 5f.12]{ref}
For example, the <complete graph> $K_4$ joins every pair of four <vertices>, giving six <edges>. Put its <vertices> at the corners of a square and its diagonals cross. Instead put $A,B,C$ at the corners of a <triangle> and $D$ inside it: the same six <edges> $AB,AC,BC,AD,BD,CD$ now meet only at their endpoints. The first <graph drawing> obscures planarity; the second proves it. In particular, its <crossing number> is zero.
\Image[/complete-four-vertex-graph-crossing-and-plane-drawings.png]
{title=The same complete graph on four vertices drawn with a crossing and with four faces}
{id=complete-four-vertex-graph-crossing-and-plane-drawings}
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.
Back to article page
