Planare Graphen - Eine interaktive Einführung

1. Was ist ein planarer Graph?

Wähle einen Graphen. Ist er planar? Verschiebe die Knoten.
Planare Graphen sind eine Unterkategorie von Graphen mit speziellen Eigenschaften, die sie zu interessanten Objekten mathematischer Betrachtung machen. Mit relativ einfachen Beweisen und Sätzen kann man erstaunlich mächtige Aussagen treffen. Doch dazu später mehr. Auch konkrete Anwendungen, wie etwa das Routing von PCB-Boards sind auf planare Graphen angewiesen.

Wir wissen bereits, was ein Graph ist. Ein planarer Graph ist einfach gesagt ein Graph, welcher überkreuzungsfrei gezeichnet werden kann. Die folgende Definition ist nicht die formale Definition, sondern eine vereinfachte Variante.
Definition planarer Graph
Ein Graph $$G = (V , E )$$ heißt planar oder plättbar, wenn er eine Einbettung in die Ebene besitzt, so dass sich Kanten nur in einem Knoten schneiden. Etwas trennschärfer wird das Konzept mit der Einführung des ebenen Graphen. Diese Unterscheidung wird später noch wichtig.
Definition ebener Graph
Ein ebener Graph $$G = (V , E )$$ ist eine konkrete, überkreuzungsfreie Einbettung eines planaren Graphen in die Ebene. Betrachten wir hierzu ein Beispiel. $$K_{2,2}$$ ist ein planarer Graph, da es eine ebene Einbettung gibt. Klicke auf die grau eingefärbte Fläche, um die Animation zu starten: . Aber es gibt auch eine nicht ebene Einbettung des planaren Graphen $$K_{2,2}$$, die Überkreuzungen enthält: . Schauen wir uns $$K_4, K_5, K_6, $$ $$K_{3,3}, K_{4,4}$$ an. Welche Graphen sind planar? Können wir einen ebenen Graphen finden, um dies zu zeigen? Wir können die Knoten beliebig verschieben. Egal was wir versuchen, $$K_5, K_6, K_{3,3}, K_{4,4}$$ lassen sich nicht als ebener Graph darstellen. Es gibt keine überkreuzungsfreie Einbettung in die Ebene. Warum ist das so? Wie können wir das zeigen? Hierzu wird ein cleverer und dennoch einfacher Beweisansatz genutzt. Zeigen wir zuerst, dass $$K_{3,3}$$ nicht planar ist, also keine überkreuzungsfreie Einbettung in die Ebene existiert:

$$K_{3,3}$$ enthält einen Hamilton-Kreis $$K$$: . Betrachten wir diesen Kreis $$K$$: Er zerteilt die Ebene in zwei Flächen, eine innere und eine äußere. Wir sehen, dass dem Subgraphen der $$K$$ enthält nun noch drei weitere Kanten hinzugefügt werden müssen, um $$K_{3,3}$$ zu enthalten. Wenn wir diese Kanten auf der gleichen Seite zeichnen, überschneiden sie sich alle. Die einzige Möglichkeit eine Überschneidung zu entfernen ist eine Verlagerung einer Kante auf die andere Seite. Doch bei drei im Konflikt stehenden Kanten und nur zwei Seiten ist dies nicht möglich. Also ist $$K_{3,3}$$ nicht planar.

$$K_5$$ ist nicht planar.
Hinweise
Der Beweis für $$K_5$$ funktioniert analog. Auch bei $$K_5$$ musst du nicht lange suchen, um einen Hamilton-Kreis $$K$$ zu finden: . Betrachten wir analog diesen Kreis $$K$$: Er zerteilt wieder die Ebene in zwei Flächen. Wir sehen, dass dem Subgraphen der $$K$$ enthält nun noch fünf weitere Kanten hinzugefügt werden müssen, um $$K_5$$ zu enthalten.
Musterlösung
Wir fangen mit einem Kreis an: . Wenn ich diese Kanten auf der gleichen Seite zeichne, überschneiden sie sich in einer Weise, dass sie durch Umverlegung unmöglich überkreuzungsfrei eingezeichnet werden können. Betrachten wir dazu den Konflikt zwischen $$\{c,e\}$$ und $$\{d,b\}$$. Dieser kann nur auf zwei Arten aufgelöst werden (Fallunterscheidung):

Fall 1: Wir zeichnen $$\{c,e\}$$ aussen.
$$\Rightarrow$$ Wir können den Konflikt von $$\{b,d\}$$ u. $$\{a,c\}$$ nur lösen, indem wir $$\{a,c\}$$ außen zeichnen, da $$\{b,d\}$$ mit dem nach außen verlagerten $$\{c,e\}$$ konfligiert.
$$\Rightarrow$$ Der nun noch bestehende Konflikt zwischen $$\{a,d\}$$ u. $$\{b,e\}$$ ist nicht aufzulösen, da nun beide Kanten mit den außen gezeichneten Kanten konfligieren.
$$\Rightarrow$$ Konflikt $$\{a,d\}$$ u. $$\{b,e\}$$ kann nicht aufgelöst werden.

Fall 2: Wir zeichnen $$\{d,b\}$$ aussen.
$$\Rightarrow$$ Fall aufgrund von Symmetrie von $$K_5$$ analog zu Fall 1, nur dass hierbei der Graph um $$72$$ Grad im Uhrzeigersinn gedreht ist und die Kanten entsprechend andere sind, da sie nun relativ zu $$\{d,b\}$$ liegen.
$$\Rightarrow$$ Konflikt $$\{a,d\}$$ u. $$\{c,e\}$$ kann nicht aufgelöst werden.

Fall 1 u. Fall 2. $$\Rightarrow$$ Wir können den Konflikt zwischen $$\{c,e\}$$ und $$\{d,b\}$$ nicht auflösen ohne neue unlösbare Konflikte zu erzeugen.
$$\Rightarrow$$ $$K_5$$ hat keine überkreuzungsfreie Einbettung
$$\Rightarrow$$ $$K_5$$ ist nicht planar
Warum gilt, dass $$K_{n,m}$$ für $$n,m >= 3$$ und $$K_l$$ für $$l>=5$$ nicht planar sind?
Hinweise
Wie hängen $$K_{n,m}$$ und $$K_{3,3}$$ bzw. $$K_l$$ und $$K_5$$ zusammen?
Musterlösung
$$K_{n,m}$$ sowie $$K_l$$ gehen durch Hinzufügung von Kanten sowie Knoten aus $$K_{3,3}$$ bzw. $$K_5$$ hervor. Somit werden die bestehenden Konflikte nicht aufgelöst. Der Graph ist somit weiterhin nicht planar.

2. Der duale Graph

Hier wird der Ausgangsgraph und später auch der zugehörige duale Graph eingezeichnet.
Was mag nur ein dualer Graph sein? Wir werden ihn später verwenden, um ein Lemma zu zeigen. Doch bevor wir die zugehörige Definition verstehen, müssen wir zuerst definieren, was eine Facette bzw. Fläche eines ebenen Graphen ist.
Definition Facette
In einem ebenen Graph bezeichnet Facette (Fläche) einen von Kanten eingeschlossenen Bereich. Ebenfalls zählt hierzu die sog. äußere Facette, welche den Graphen umgibt. Anstelle einer normalen Definition, zeigen wir an Hand eines Beispiels, wie man den dualen Graphen zu einem gegebenen planaren Graphen zeichnet. Betrachten wir den rechten Graphen, wie sieht der zugehörige duale Graph aus? Er würde wie folgt eingezeichnet: Als erstes zeichnen wir in jede Facette des Graphen einen neuen Knoten: . Dieser Graph hat also vier Facetten. Als nächstes wird für jeden eine Fläche repräsentierenden Knoten, wenn diese Fläche an eine andere Fläche angrenzt, eine entsprechende Kante zwischen den jeweiligen Knoten eingezeichnet: . Nun sollte uns auch die formalere Definition verständlicher sein:
Definition Dualer Graph
Der zum ebenen Graphen $$G = (V , E )$$ ebenfalls ebene duale Graph $$G' = (V',E')$$ entsteht, indem in jeder Facette des Graphen $$G$$ neue Knoten $$v'$$ hinzugefügt werden und für jede Kante $$e \in E$$ eine neue Kante $$e'$$ erstellt wird, die die $$v'$$ der beiden angrenzenden Facetten verbindet. Jede Facette besitzt eine Länge, die wie folgt definiert wird:
Definition (Länge von Facetten)
Die Länge einer Facette eines ebenen Graphen entspricht der Gradzahl des entsprechenden Knotens des zugehörigen dualen Graphen. Wir bezeichnen die Facetten in obigem Beispiel der Einfachheit halber einfach mit dem Namen des korrespondierenden Knoten. In unserem Beispiel hat also die Facette $$a'$$ die Länge 2, $$b'$$ die Länge 3 usw..

Beweise das Duale Handshaking-Lemma: Sei $$l(F_i)$$ die Länge der Facette $$F_i$$ eines ebenen Graphen $$G$$, so gilt: $$\sum\limits_{F_i \in F(G)} l(F_i) = 2 · |E (G )|$$
Hinweise
Betrachte das Handshaking-Lemma: $$\sum\limits_{v \in V(G)} deg(v) = 2 · |E(G)|$$, wie hängt es mit dem dualen Graphen zusammen?
Musterlösung
Für einen Graphen $$G$$ gilt das Handshakinglemma: $$\underset{v \in V(G)}{\sum} deg(v) = 2 · |E(G)|$$

Sei $$G^*$$ der duale Graph zu $$G$$

$$\Rightarrow \sum\limits_{v \in V(G^*)} deg(v) = 2 · |E(G^*)|$$
$$\Leftrightarrow \sum\limits_{F_i \in F(G)} l(F_i) = 2 · |E(G^*)|$$
$$\Leftrightarrow \sum\limits_{F_i \in F(G)} l(F_i) = 2 · |E(G)|$$
q.e.d.

3. Die Euler-Charakteristik

Wir haben zuvor gezeigt, dass $$K_6$$ und $$K_7$$ nicht planar sind. Dies gilt jedoch nicht für $$K_6$$ in der projektiven Ebene oder etwa $$K_7$$ im Torus.
Eine für viele Beweise sehr hilfreiche Eigenschaft planarer Graphen ist, dass alle ebenen Einbettungen dieser die von Leonhard Euler 1750 (wieder-)entdeckte Formel erfüllen.
Definition Euler-Charakteristik (f. planare Graphen)
Für einen zusammenhängenden, ebenen Graphen $$G$$ mit $$n$$ Knoten, $$e$$ Kanten und $$f$$ Facetten gilt: $$n − e + f = 2$$ Der Beweis der Eulercharakteristik für einen ebene Graphen $$G$$ erfolgt per Induktion über die Kantenzahl $$e$$. Im Folgenden ist eine Beweisskizze dargestellt.

IA: ($$e=0$$)

Da der Graph zusammenhängend ist folgt hieraus, dass die Knotenzahl $$n=1$$ und somit die Facettenzahl $$f=1$$ ist. Also gilt $$n - e + f = 1 - 0 + 1 = 2$$ und somit die Euler-Charakteristik.

IS: ($$e>=1$$)

Ist $$G$$ ein Baum, dann ist $$e=n-1$$ und $$f=1$$ und somit gilt $$n - e + f = n - (n-1) + 1 = n-n+1+1 = 2$$. Ist $$G$$ kein Baum, so sei $$k$$ eine Kante, die auf einem Kreis von $$G$$ liegt. Graph $$G$$ muss einen Kreis enthalten, da er sonst nach Definition ein Baum wäre. Betrachte $$G' = G-k$$: Der zusammenhängende, ebene Graph $$G'$$ hat nun $$n$$ Knoten, $$e-1$$ Kanten und $$f-1$$ Facetten. Der Zusammenhang bleibt erhalten, da lediglich eine Kante aus einem Kreis entfernt wird und die durch diese Kante verbundenen Knoten über den Rest der Kanten im vorherigen Kreis weiterhin mit allen Knoten verbunden bleiben. Der Graph ist weiterhin eben, da dem Graphen lediglich eine Kante entfernt wird, also keine neue Kante eine Überkreuzung erzwingen kann. Die Facettenzahl reduziert sich um $$1$$, da das Entfernen der Kante einen Kreis öffnet und somit die vorherig von ihm eingeschlossene Facette nicht mehr besteht. Nach Induktionsvoraussetzung gilt für $$G'$$ die Euler-Charakteristik, also $$n - (e-1) + (f-1) = 2 \Leftrightarrow n - e + f = 2$$. Also gilt die Euler-Charakteristik auch für $$G$$.
Sei $$G$$ ein einfacher, ebener Graph mit mindestens drei Knoten, dann gilt $$|E (G )| \leq 3|V (G )| − 6$$.
Hinweise
Nutze das duale Handshake-Lemma: $$\sum l(F_i ) = 2 · |E (G )|$$, wobei $$l(F_i)$$ die Länge der Facette $$F_i$$ bezeichnet.
Musterlösung
Wir wollen zeigen, dass $$e \leq 3n - 6$$.

Aus $$\sum l(F_i ) = 2 · |E (G )|$$ folgt $$3 f \leq 2 · |E (G )|$$, da in einem einfachen Graphen – also ohne Mehrfachkanten – jede Facette von Mindestens 3 Kanten umschlossen wird.

Betrachten wir nun die Eulercharakteristik und formen diese äquivalent um, um $$f$$ zu ersetzen: $$n - e + f = 2 \Leftrightarrow 3n - 3e + f = 6$$. Setzen wir nun obige Ungleichung ein: $$6 = 3n - 3e + 3f \leq 3n - 3e + 2e$$

$$\Rightarrow 6 \leq 3n - 3e + 2e \Leftrightarrow e \leq 3n - 6$$.

Somit haben wir mit Hilfe der Eulercharakteristik gezeigt, dass in jedem planaren Graphen die Kantenzahl durch die Knotenzahl linear beschränkt wird (anders als bei nichtplanaren Graphen).
Ende des Lehrinhalts, unten findest du weiterführendes Material

I. Quellen und weiterführendes Material

Neben zahlreichen Wikipedia-Artikeln aus dem Themengebiet der Graphentheorie existieren weitere Ressourcen, die ich zum tiefergehenden Studium besonders empfehle:

R. Diestel - Graphentheorie (Springer, 2000)
Standardwerk mit allen Termini, wichtigen Beweisen und Aufgaben.
Douglas B. Wests - Introduction to Graph Theory (Prentice Hall, 2001)
Standardwerk (Englisch) mit allen Termini, wichtigen Beweisen und Aufgaben.