# Kreuzungsfreie Graphen

In der Praxis ist es oft wichtig, einen Graphen so in der Ebene anzuordnen, dass sich keine Kanten kreuzen. Ein typisches Beispiel: Leiterbahnen auf einer Platine.

Betrachten Sie bitte den „vollständigen Graphen“ K4, bei dem jeder der vier Knoten mit jedem anderen verbunden ist:

    Graph.complete(4).display()

Hier kreuzen sich zwei Kanten. Aber das lässt sich ändern: Klicken Sie bitte in der Symbolleiste des Grapheneditors auf das Zeigefingersymbol und schieben Sie dann z.B. den Knoten 3 nach oben (in das Dreieck 4,1,2). Der Graph K4 kann also ohne Kreuzungen dargestellt werden.

Definition

Ein Graph heißt planar (oder plättbar), wenn er sich ohne Kreuzungen in der Ebene darstellen lässt.

Nun betrachten Sie bitte den „vollständigen bipartiten Graphen“ K3,2, bei dem die Knoten aus zwei Gruppen (mit 3 und 2 Mitgliedern) bestehen, so dass jeder Knoten genau mit jedem Knoten der anderen Gruppe verbunden ist:

    Graph.completeBipartite(3,2).display()

Sicher gelingt es Ihnen auch hier, die Knoten so zu verschieben, dass keine Kreuzung mehr übrig bleibt: Der K3,2 ist also ebenfalls ein planarer Graph!

Jetzt kommt eine schwierigere Aufgabe. Versuchen Sie sich an dem Graphen K5:

    Graph.complete(5).display()

Haben Sie es geschafft, die anfänglich 5 Kreuzungen auf eine zu reduzieren? Dann herzlichen Glückwunsch! Besser geht es nicht. Der K5 ist nämlich nicht planar!
Bisher haben wir den Nachweis der Planarität durch erfolgreiches Probieren bewiesen. Misserfolg nach langem Probieren ist natürlich kein Beweis, dass es nicht doch geht. Jetzt müssen wir wirklich mathematisch an das Problem herangehen.

## Zwei Beispiele für nicht planare Graphen

### K5 ist nicht planar!

Wir nehmen einmal an, der K5 wäre planar.
Dann würde eine kreuzungsfreie Darstellung die Ebene in Gebiete zerlegen, für deren Anzahl g nach dem eulerschen Polyedersatz

g = k - e + 2
gilt, wobei k die Anzahl der Kanten und n die Anzahl der Knoten (Ecken) ist.
In unserem Fall ist also
g = 10 - 5 + 2 = 7
a sei die durchschnittliche Anzahl der Kanten um ein Gebiet.
Jedes Gebiet wird von mindestens 3 Kanten umrandet. Also ist
\def\pink{\bbox[#ffe0e0,2pt]} \pink{a \ge 3}
Da jede Kante an zwei Gebiete grenzt, gilt
\def\pink{\bbox[#ffe0e0,2pt]} \pink{a} = \frac{2 k}g = \frac{20}7 \pink{< 3}
Die beiden Ungleichungen widersprechen sich. Demnach war unsere Annahme (K5 wäre planar) falsch.

### K3,3 ist nicht planar!

Auch an diesem Graphen werden Sie verzweifeln, wenn Sie versuchen, ihn kreuzungsfrei zu machen:

    Graph.completeBipartite(3,3).display()

Der K3,3 wird auch als „Versorgungsgraph“ bezeichnet.

Man kann nämlich die eine Dreiergruppe als Häuser ansehen und die andere z.B. als Wasserwerk, E-Werk und Gaswerk und versuchen, alle Zuleitungen kreuzungsfrei zu verlegen.

Der Beweis, dass der K3,3 nicht planar ist, klappt ebenso wie beim K5. Einziger Unterschied: Da die Kanten immer zwischen zwei Gruppen wechseln, muss jedes Gebiet von einer geraden Zahl von Kanten umgeben sein und daher von mindestens vier Kanten!

## Der Satz von Kuratowski

Wir haben gerade zwei Beispiele für nicht planare Graphen gefunden. Der polnische Mathematiker Kazimierz Kuratowski veröffentlichte 1930 einen erstaunlichen Satz. Danach haben unsere beiden Beispiele eine ganz besondere Bedeutung: Mindestens eines dieser beiden Beispiele steckt nämlich in in jedem nicht planaren Graphen!

Satz von Kuratowski

Ein Graph ist planar genau dann, wenn er keinen Teilgraphen besitzt, der eine Unterteilung von K3,3 oder K5 ist.

Eine Unterteilung entsteht, wenn man auf einer Kante einen neuen Knoten einfügt (und damit die Kante in zwei Kanten zerlegt). Wir schauen uns das an einem Beispiel an:

### Beispiel: Der Petersen-Graph

    G = Graph.fromShortRepr("""
        1,170,20; 2,313,124; 3,258,291; 4,82,291; 5,27,124;
        6,170,90; 7,241,147; 8,214,231; 9,126,231;10,99,147;
        -1,490,290; -2,620,20; -3,620,164; -4,620,290; -5,360,20;
        -6,490,20; -7,585,57; -8,395,220; -9,586,220; -10,360,290|
        1,6; 1,5; 1,2; 2,3; 2,7; 3,4; 3,8; 4,5; 4,9; 5,10; 6,8; 6,9; 7,9; 7,10; 8,10""")
    G.display()

Obwohl dieser „Petersen-Graph“ dem K5 sehr ähnlich sieht (ignorieren Sie bitte zunächst die grauen Knoten!), steckt im Sinne von Kuratowski der K5 nicht darin!

Bitte schieben Sie nun alle Knoten des Petersen-Graphen (1 bis 10) möglichst genau über die grauen Pendants mit den negativen Nummern.

Das Ergebnis sieht dem K3,3 ähnlich! Löschen Sie bitte die Kanten zwischen den Knoten 3 und 8 sowie zwischen den Knoten 7 und 9.
Der verbliebene Teilgraph ist eine Unterteilung des Graphen K3,3 (die vier Kanten {2,4}, {2,10}, {4,6} und {6,10} sind unterteilt).

Nach dem Satz von Kuratowski ist der Petersen-Graph also nicht planar.