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 the Polish mathematician Kazimierz Kuratowski in 1930, now known as Kuratowski's theorem:

  • A finite graph is planar if and only if it does not contain a subgraph that is a subdivision of K_5 or K_{3,3}.

A subdivision of a graph results from inserting vertices into edges zero or more times.

Instead of considering subdivisions, Wagner's theorem deals with minors:

  • A finite graph is planar if and only if it does not have K_5 or K_{3,3} as a minor.

A graph H is a minor of a graph G if a copy of H can be obtained from G via repeated edge deletion and/or edge contraction.