Graph Theory/Planar Graphs

From Wikibooks, open books for an open world
Jump to: navigation, search

Planar Graphs[edit]

Definition[edit]

A planar graph is a graph that can be drawn in the plane such that there are no edge crossings.

Characterization[edit]

The planar graphs can be characterized by a theorem first proven by Kazimierz Kuratowski in 1930, which states that the planar graphs are exactly those graphs G such that K_5 \not \preceq G and K_{3,3} \not \preceq G .