Unterteilung (Subdivision) und Satz von Kuratowski

Der Satz von Kuratowski liefert eine rein kombinatorische, strukturelle Charakterisierung der Planarität ohne Rückgriff auf topologische Zeichnungen.

Unterteilung (Subdivision): Ein Graph $G^{'}$ ist eine Unterteilung eines Graphen $G$ , wenn $G^{'}$ aus $G$ durch das sukzessive Ersetzen von Kanten durch Pfade der Länge $> 0$ entsteht. Die eingefügten inneren Knoten der neuen Pfade müssen vom Grad $2$ sein und dürfen keine gemeinsamen Schnittpunkte untereinander besitzen.
Satz von Kuratowski: Ein Graph $G$ ist genau dann planar, wenn er keinen Untergraph enthält, der eine Unterteilung des vollständigen Graphen $K_{5}$ oder des vollständigen bipartiten Graphen $K_{3, 3}$ darstellt. $K_{5}$ und $K_{3, 3}$ bilden die minimalen, nicht-planaren strukturellen Hindernisse.