Planare Graphen

In diesem Abschnitt kann man sich auf die Betrachtung ungerichteter Graphen beschränken, weil ein gerichteter Graph genau dann planar ist, wenn der zugehörige ungerichtete Graph planar ist.

1. Ebener Graph und planarer Graph:

Ein ebener Graph ist ein derart in die Ebene gezeichneter Graph, daß die Schnittpunkte der Kanten stets in Knoten des Graphen liegen.
Ein zu einem ebenen Graphen isomorpher Graph heißt planar. Die linke Abbildung zeigt einen ebenen Graphen die rechte Abbildung einen zu G₁ isomorphen Graphen der nicht eben, wegen der Isomorphie zu G₁ aber planar ist.

2. Nichtplanarer Graph:

Der vollständige Graph K₅ und der vollständige paare Graph K_3,3 sind nichtplanare Graphen.

3. Unterteilungen:

Man erhält eine Unterteilung eines Graphen indem man auf Kanten von G Knoten vom Grad 2 einfügt. Jeder Graph ist eine Unterteilung von sich selbst. In den folgenden beiden Abbildungen sind Unterteilungen der Graphen K₅ bzw. K_3,3 dargestellt.

4. Satz von Kuratowski:

Ein Graph ist genau dann nichtplanar, wenn er eine Unterteilung des vollständigen paaren Graphen K_3,3 oder eine Unterteilung des vollständigen Graphen K₅ als Untergraph enthält.