Skip to main content
Post Made Community Wiki by S. Carnahan
Source Link
David Eppstein
  • 18.6k
  • 2
  • 55
  • 127

A few reasons for the importance of planarity having little to do with the need for maps:

  • A matroid is both graphic and co-graphic if and only if it is the graphic matroid of a planar graph

  • Planar graphs are the graphs with Colin de Verdiere invariant ≤ 3. As such they form a sequence with the trees, outerplanar graphs, planar graphs, and linklessly embeddable graphs.

  • The graphs of three-dimensional convex polyhedra are exactly the 3-connected planar graphs (Steinitz's theorem).

  • A minor-closed graph family has bounded treewidth if and only if it does not include all the planar graphs.