Planarität & Crossingnumbers & Satz von Kuratowski

Im nachfolgenden Applet kann man anhand einiger interessanter Beispiele versuchen die Crossing Number der jeweiligen Graphen zu bestimmen. Die Crossing Number ist die von der gewählten Einbettung des jeweiligen Graphen unabhängige Zahl minimaler Kantenüberschneidungen. Ist die Crossing Number $0$ so nennt man den Graph planar.

Satz von Kuratowski

Satz (1930): Ein endlicher Graph ist genau dann planar, wenn er keinen Teilgraphen enthält, der durch Unterteilung von oder entstanden ist.

Bemerkungen: Ein Graph $U$ ist eine Unterteilung eines Graphen $T$, falls man grob gesprochen $T$ aus $U$ erhält, in dem man endlich oft (auch null mal) neue Knoten auf den Kanten von $T$ plaziert. Kann man also beginnend mit einem der Graphen oder , durch Hinzufügen von Knoten auf bestehenden Kanten dieses Graphens einen Subgraph von $G$ identifizieren, so kann $G$ nicht planar einbettbar sein.

Eine Variante dieses Satzes ist der Satz von Wagner: Ein Graph $G$ ist genau dann planar, wenn weder noch ein Minor von $G$ ist.

Bemerkungen: Ein Graph $M$ ist ein Minor eines Graphen $G$, falls man diesen grob gesprochen durch das Verschmelzen von Knoten in $G$ erhalten kann. Beim -Graph ist dies z.B. gut zu erkennen (Verschmelze der Reihe nach die Knotenpaare $(A,F), (B,G), (C,H), (D,I)$ und $(E,J)$).

Zur Bedienung des Applets:

• Analog zum Applet auf Was ist ein Graph?.
• Das “Verschmelzen” von Knotenpaaren lässt sich optisch durch das Aufeinanderlegen zweier Knoten simulieren.

GraphPlanarity.cdy (Dieses Applet kann in Cinderella ausgeführt werden.)