11 Planare Graphen

Topologische Vorbereitung

Definition 11.1

Ein Polygon in der euklidischen Ebene \(\R^2\) ist eine zum Einheitskreis homöomorphe, abgeschlossene Teilmenge von \(\R^2\), die die Vereinigung endlich vieler Strecken ist.

Ein Polygonzug ist eine zum abgeschlossenen Einheitskreisintervall \([0,1]\) homöomorphe Teilmenge von \(\R^2\), die die Vereinigung endlich vieler Strecken ist.

Für einen Polygonzug \(X\) notieren wir mit \(\mathring X\) den Polygonzug ohne seine Endpunkte.

Sei \(\sigma\subseteq\R^2\) offen. Die durch Polygonzüge in \(\sigma\) definierte Äquivalenzrelation auf \(\sigma\) zerlegt \(\sigma\) in Äquivalenzklassen, die wir Gebiete nennen (offene, wegzusammenhängende Teilmengen).

Ist \(X\subseteq\sigma\) abgeschlossen und \(y_1,y_2\) liegen in verschiedenen Gebieten von \(\sigma\backslash X\), so trennt \(X\) die Punkte \(y_1\) und \(y_2\) in \(\sigma\).

Der Rand einer Menge \(X\subseteq\R^2\) ist \[ \partial X \;=\;\{\,y\in\R^2\mid\text{jede Umgebung von }y\text{ trifft sowohl }X\text{ als auch }\R^2\backslash X\}. \]

Ist \(X\) offen, liegt \(\partial X\subseteq\R^2\backslash X\).

Lemma 11.2

Ist \(X\) die Vereinigung endlich vieler Strecken und Punkte, \(f\) ein Gebiet von \(\R^2\backslash X\), und \(x\in X\cap\partial f\), dann existiert eine Strecke zwischen \(x\) und einem Punkt in \(f\), deren Inneres vollständig in \(f\) liegt.

Ohne Beweis.

Lemma 11.3

Sei \(\sigma\subseteq\R^2\) offen und \(\phi\colon[0,1]\to P\subseteq\R^2\) ein Homöomorphismus mit \(\phi(0)\in\sigma\) und \(\phi(1)\notin\sigma\).
Dann gibt es einen eindeutig bestimmten Parameterwert \[ y=\sup\{\,t\in[0,1]\mid \phi([0,t])\subseteq\sigma\}, \] bis zu dem die Kurve vollständig in \(\sigma\) verläuft. Also:

Für \(t<y\): \(\phi(t)\in\sigma\).
Für \(t>y\): \(\phi(t)\notin\sigma\).
Bei \(t=y\): \(\phi(y)\in\partial\sigma\).

Mit anderen Worten: Die Kurve trifft an \(\phi(y)\) erstmals \(\partial\sigma\) und verläuft danach in \(\R^2\backslash\sigma\).

Satz 11.4 (Jordanscher Kurvensatz für Polygone)

Ist \(P\subseteq\R^2\) ein Polygon, so hat \(\R^2\backslash P\) genau zwei Gebiete, von denen genau eines beschränkt ist. \(P\) ist der Rand beider Gebiete.

Lemma 11.5

Seien \(P_1,P_2,P_3\) drei disjunkte Polygonzüge mit gemeinsamen Endpunkten.

\(\R^2\backslash(P_1\cup P_2\cup P_3)\) hat genau drei Gebiete mit Rändern \(P_1\cup P_2\), \(P_2\cup P_3\), \(P_1\cup P_3\).
Ist \(P\) ein Polygonzug von \(\mathring P_1\) nach \(\mathring P_3\), dessen Inneres im Gebiet von \(\R^2\backslash(P_1\cup P_2\cup P_3)\) liegt, das \(\mathring P_2\) enthält, dann gilt \(\mathring P\cap\mathring P_2\neq\emptyset\).

Satz 11.6

Sind \(X_1,X_2\subseteq\R^2\) disjunkt und je Polygonszüge, deren Inneres \(\mathring P\) ohne Schnittpunkte ganz in einem Gebiet \(\sigma\) von \(\R^2\backslash(X_1\cup X_2)\) liegt, dann ist \(\sigma\backslash\mathring P\) ein Gebiet von \(\R^2\backslash(X_1\cup P\cup X_2)\).

Ebene Graphen

Definition 11.7 (Ebene Graphen)

Ein ebener Graph (engl. plane graph / planar embedding) ist ein Paar \((V,E)\) mit endlichen Mengen, sodass

\(V\subseteq\R^2\) die Knoten sind,
jede Kante \(e\in E\) ein Polygonzug zwischen zwei Knoten,
das Innere jeder Kante weder Knoten noch Punkte innerer Kanten enthält (keine Schnittpunkte).

Für einen ebenen Graphen \(G\) ist \(\R^2\backslash G\) offen, deswegen die Gebiete von \(\R^2\backslash G\) heißen Gebiete von \(G\). Es gibt genau ein Außengebiet; alle anderen heißen Innengebiete.

Die Menge der Gebiete bezeichnen wir mit \(F(G)\) (engl. faces).
Den Rand eines Gebietes \(f\in F(G)\) notieren wir als \(G[f]\).

Satz 11.8

Sei \(G\) ein ebener Graph und \(e\in E(G)\) eine Kante.

Für alle \(f\in F(G)\) gilt entweder \(e\subseteq G[f]\) oder \(\mathring e\cap G[f]=\emptyset\).
\(e\) liegt auf dem Rand mindestens eines und höchstens zweier Gebiete.
(-) Liegt \(e\) auf einem Kreis \(C\subseteq G\), so liegt \(e\) auf dem Rand genau zweier Gebiete, die in verschiedenen Gebieten von \(C\) liegen.
(-) Liegt \(e\) auf keinem Kreis, so ist \(e\) eine Brücke und liegt auf dem Rand genau eines Gebietes.

Beweis

Sei \(x\in\mathring e\). Wähle eine offene Kreisscheibe \(D_x\) um \(x\), die ein oder zwei Teilstrecken von \(\mathring e\) trifft. Dann ist \(D_x\backslash G\) die Vereinigung zweier offener Halbscheiben, jede in einem Gebiet \(f_1,f_2\). Aus Satz 11.4 folgt \(f_1\neq f_2\) genau dann, wenn \(e\) auf einem Kreis liegt; sonst \(f_1=f_2\) nach Satz 11.6. Da Äquivalenzklassen konstant bleiben, gibt es keine weiteren Gebiete.

Korollar 11.9

\(G[f]\) definiert stets einen Teilgraphen von \(G\).

Lemma 11.10

Sei \(G\) ein ebener Graph, \(f\in F(G)\) und \(H\subseteq G\). Dann gilt:

\(f\) liegt in einem Gebiet \(f'\in F(H)\).
Ist \(G[f]\subseteq H\), so \(f=f'\).

Beweis

Gebiete können nicht schrumpfen.
Wäre \(f\neq f'\), gäbe es einen Polygonzug von \(f\) nach \(f'\backslash f\), der nach Lemma 11.3 \(\partial f\) trifft, also in \(H\) liegt – Widerspruch.

Korollar 11.11

Ein ebener Wald hat genau ein Gebiet.

Beweis

Jede Kante ist eine Brücke.

Satz 11.12

Hat ein ebener Graph zwei verschiedene Gebiete mit demselben Rand, so ist der Graph ein Kreis.

Beweis: Sei \(H=G[f_1]=G[f_2]\) der gemeinsame Rand zweier Gebiete.

Nach Lemma 11.10 sind \(f_1,f_2\) Gebiete von \(H\). Aus Korollar 11.11 folgt, dass \(H\) einen Kreis \(C\) enthält. Satz 11.8(iii) liefert, dass \(f_1,f_2\) in verschiedenen Gebieten von \(C\) liegen. Da \(f_1\cup f_2\cup H=\R^2\) und \(g_1\cup g_2\cup C=\R^2\), folgt \(H=C\) und damit \(G=C\).

Satz 11.13

In einem 2-zusammenhängenden ebenen Graphen ist jedes Gebiet kreisberandet.

Beweis: Sei \(G\) 2-zusammenhängend, \(f\in F(G)\).

Enthält \(G[f]\) einen Kreis, folgt mit Korollar 11.11 \(f\cup G[f]=\R^2\). Andernfalls wäre \(G[f]\) ein Baum, Widerspruch. Enthält \(G[f]\) einen Kreis \(C\neq G[f]\), so findet man einen C-Weg \(P\) in \(G[f]\), sodass \(H=C\cup P\subseteq G\). Dann stünden \(C\cup P\) im Widerspruch zu Lemma 11.5, da drei Gebiete entstünden.

Satz 11.14

Die Gebietsränder eines 3-zusammenhängenden ebenen Graphen sind genau seine nicht-trennenden induzierten Kreise.

Beweis

\((\Leftarrow)\): Sei \(G\) 3-zusammenhängend und \(C\subseteq G\) ein induzierter Kreis, der nicht trennt. Nach Satz 11.4 liegen alle Punkte von \(\R^2\backslash C\) auf einer Seite, daher ist \(C\) ein Gebietsrand.

\((\Rightarrow)\): Umgekehrt, sei C ein Rand eines Gebietes von G. Nach dem Satz 11.13 ist C ein Kreis. Zu zeigen: C ist induziert, C ist kein Trenner. Angenommen, C hat eine Sehne \(e = \{x,y\}\). Die Komponente \(C_1\) und \(C_2\) von \(C - \{x,y\}\) sind in \(G - \{x,y\}\) nicht getrennt, da G 3-zusammenhängend ist. Also gibt es ein Weg von \(C_1\) nach \(C_2\). Da f ein Gebiet mit \(G[f] = C\) ist, läuft der Weg durch das „innere“ Gebiet \(\R^2 - (C\cup f)\), so wie \(\{x,y\}\) auch, jedoch ohne einander zu treffen. Dies widerspricht Lemma 11.5(ii). Also C ist induziert.

Nehmen wir jetzt an, dass C zwei Kanten \(p,q \in G - C\) trennt. Es gibt nach Menger drei Kruezungsfreie Wege zwischen p und q. Das Gebiet f ist in einer der 3 Gebiete dieses Teilgraphen enthalten. Der dritte Weg bleibt p und q verbunden in \(G - C\), also C ist ein Trenner.

Definition 11.15

Ein ebener Graph G heißt maximal eben, wenn wir ihn nicht durch hinzufügen von neuen (ebenen) Kanten zu einem ebenen Graph \(G^\prime \supseteq G\) mit \(V(G) = V(G^\prime)\) erweitern können.

Definition 11.16

G heißt ebener Dreiecksgraph, wenn jedes seiner Gebiete durch ein \(K_3\) berandet ist.

Beispiel

Der Goldner–Harary Graph ist maximal planar. Jedes Gebiet wird von drei Kanten umrandet.

Satz 11.17

Ein ebener Graph G mit \(n(G) \geq 3\) ist genau dann maximal eben, wenn G ebener Dreiecksgraph ist.

Beweis

Sei G ein ebener Graph mit \(n(G) \geq 3\).

\((\Leftarrow)\) Ist jedes Gebiet durch ein \(K_3\) umrandet können wir nirgendwo eine Kante hinzufügen, da G einfach ist.

\((\Rightarrow)\) Umgekehrt, sei G maximal eben, \(f \in F(G)\) und \(H := G[f]\). Der Graph \(G[H]\) (induziert von H) ist vollständig, da sonst ein Polygonzug durch f zwischen zwei nicht benachbarten Knoten von H gewählt werden kann. Also \(G[H] = K_n\) für \(n \in \N\).

Angenommen, H enthält keinen Kreis. Dann ist H ein Baum und \(f \cup H = \R^2\) (nach Lemma 11.3?). Also ist \(G = H\) und da \(n(G) \geq 3\) können weitere Kanten hinzufügt werden, was ein Widerspruch ist. Also H enthält doch einen Kreis.

Angenommen, \(n \geq 4\). Da \(G[H]\) vollständig ist, gibt es wiederum einen Widerspruch zu Lemma 11.5(ii). Also ist \(n \leq 3\) und damit \(H = K_3\).

Satz 11.18 (Eulersche Polyederformel für die Ebene)

Ist G ein zshgd ebener Graph mit \(n \geq 1\) Knoten, m Kanten und l Gebiete, so gilt \[ n - m + l = 2\] Also |Vertices| - |Edges| + |Faces| = 2.

Beweis

Gegeben n. Wir verwenden die Induktion nach m. Wenn \(m \leq n - 1\) (also \(m = n - 1\) wegen Zshg), ist G ein Baum. Ein Baum hat \(l = 1\) Gebiet: \[ n - m + l = n - (n - 1) + 1 = 2 \] Sei also \(m \geq n\) und e eine Kante die auf einem Kreis kiegt: \(G^\prime := G - e\). Satz 11.8 sagt, dass e auf dem Rand zweier Gebiete \(f_1\) und \(f_2\) liegt. In \(G^\prime\) gilt \(f^\prime = f_1 \cup f_2 \cup \mathring{e}\). Zudem gilt, dass \[ F(G) - \{f_1, f_2\} = F(G^\prime) - \{f^\prime\} \] Also ist \(l(G) = l(G^\prime) + 1\) und \(m(G) = m(G^\prime) + 1\). Es gilt damit: \[ n(G) - m(G) + l(G) = n(G^\prime) - (m(G^\prime) + 1) + (l(G^\prime) + 1) = 2 \]

Korollar 11.19

Ein ebener Graph mit \(n \geq 3\) Knoten hat höchstens \(3n - 6\) Kanten,
Und damit insbesondere hat jeder ebene Dreiecksgraph genau \(3n - 6\) Kanten.

Beweis

Für Dreiecksgraphen gilt \(2m = 3l\). Also \(l = \frac{2}{3}m\). Dann folgt \[ n - m + \frac{2}{3}m = 2 \eq \frac{1}{3}m = n - 2 \eq m = 3n - 6 \]

Korollar 11.20

Kein ebener Graph enthält \(K_5\) oder \(K_{3,3}\) als topologischen Minor.

Beweis

\(K_5\) ist nicht plättbar, denn ein ebener Graph mit \(n=5\) Knoten und \(m=10\) Kanten würde nach der Abschätzung
\[m\le3n-6=3\cdot5-6=9\]
höchstens 9 Kanten haben in Widerspruch zu \(m=10\).
\(K_{3,3}\) ist nicht plättbar, denn ein ebener Graph mit \(n=6\), \(m=9\) hätte nach der Eulerschen Formel
\[F=2-n+m=2-6+9=5\]
Gebiete. Als bipartiter Graph enthält \(K_{3,3}\) keine ungeraden Zyklen, also hat jede Fläche mindestens 4 Seiten. Damit
\[\sum_{f}\deg(f)\ge5\cdot4=20,\quad\text{aber}\quad2m=18,\]
was widerspricht.

Beispiel

Die folgende Landnachbarschaftrelation einer hypothetischen Landkarte kann nicht planar dargestell werden, da sie ein vollständiger \(K_5\) Graph vorstellt.

11 Einbettungen und Plättbarkeit

Definition 11.21

Eine Einbettung in die Ebene eines (normalen) Graphen \(G\) ist ein Isomorphismus zwischen G und einen ebenen Graphen \(\tilde{G}\).
Der ebene Graph \(\tilde{G}\) selbst nennen wir dann eine Zeichnung von \(G\).
Ein Graph \(G\) heißt plättbar (planar), wenn er in die Ebene einbettbar ist.
\(G\) heißt maximal plättbar, wenn G plättbar ist, aber \(G + e\) für jede neue Kante \(e\) nicht.

Satz 11.22

Jeder maximal ebener Graph ist maximal plättbar.
Ein plättbarer Graph mit \(n \geq 3\) ist genau dann maximal plättbar, wenn er \(3n - 6\) Kanten hat.

Beweis

Folgt direkt aus dem Satz 11.17 und Korolar 11.19.

Satz 11.23 (Kuratowski, 1930; Wagner, 1937)

Die folgenden Aussagen sind äquivalent für Graphen G.

G ist plättbar
G enthält weder einen \(K_5\) noch einen \(K_{3,3}\) als Minor
G enthält weder einen \(K_5\) noch einen \(K_{3,3}\) als topologischer Minor.

Beweis

folgt für 3-zshgd Graphen aus nachfolgenden Lemata.

Beispiel

Der Petersen-Graph enthält den vollständig bipartiten Graphen als Minor und ist deshalb nicht planar.

Lemma 11.24

Ein Graph enthält genau dann einen \(K_5\) oder \(K_{3,3}\) als Minor, wenn er einen \(K_5\) oder \(K_{3,3}\) als topologischen Minor enthält.

Beweis

Wir wissen schon, dass topologischer Minor einen normalen Minor entspricht, und dass \(K_{3,3}\) als Minor auch \(K_{3,3}\) als topologischen Minor enthält (nach dem Satz 6.5).

z.z.: \(G\) enthält \(K_5\) als Minor \(\Rightarrow\) \(G\) enthält \(K_5\) oder \(K_{3,3}\) als topologischen Minor.

Idee:

Zuerst entfernen wir möglichst viele Kanten und Knoten ohne \(K_5\) als Minor zu verlieren. Dann induziert jede Verzweigungsmenge einen Baum.

Dann induziert jede Verzweigungsmenge einen Baum und es gibt genau eine Kante zwischen jedes Paar der Verzweigungsmengen.

Der Baum einer Verzweigungsmenge ergänzt um den Kanten zu den anderen Mengen ist ein Baum mit 4 Blätter. Entweder hat dieser Baum ein Knoten von Grad 4 (uns hat \(K_{1,4}\) als top. Minor) oder genau zwei Knoten vom Grad 3. Gilt ersteres für alle Verzweigungsmengen, enthält G ein \(K_5\) als top. Minor. Gilt letzteres für mindestens eine Verzweigungsmenge, ist \(K_{3,3}\) ein top. Minor.

Lemma 11.25

Ist G ein 3-zshgd. Graph und enthält G weder ein \(K_5\) noch ein \(K_{3,3}\) als Minor, so ist plättbar.

Beweis

Mit Induktion nach \(n(G)\):

(IA) Für \(n(G) = 4\) ist \(G = K_4\) und hat weder \(K_5\) noch \(K_{3,3}\) als Minor, ist aber plättbar.

(IS) Sei jetzt die Aussage wahr für alle Graphen mit höchstens \(n(G) - 1\) Knoten. Satz 10.5 besagt, dass G eine Kante xy mit der Eigenschaft hat, dass \(G/xy\) wieder 3-zshgd ist und nach Induktionsvoraussetzung plättbar ist.

Sei \(\tilde{G}\) eine Zeichnung von \(G/xy\). Sei f das Gebiet von \(\tilde{G} - v_{xy}\) mit \(v_{xy} \in f\) und \(C := (\tilde{G} - v_{xy})[f]\). Definiere dann: \[ X := N_G(x) - \{y\}, Y := N_G(y) - \{x\} \] Es gilt dann \(X \cup Y \subseteq V(C)\).

Weiter ist \(\tilde{G} - v_{xy}\) 2-zshgd. (da \(\tilde{G})\) zshgd). Nach Satz 11.13 ist C ein Kreis.

Seien \(x_1, \dots, x_k\) die Knoten in natürlicher Reihenfolge entlang C und \(P_i = x_i \dots x_{i + 1}\) ihrer Verbindungsmenge mit \(x_{k+1} = x_1\)

Sei \(\tilde{G}^\prime := \tilde{G} - \{v_{xy}w \text{ : } w \in Y - X\}\). \(\tilde{G}^\prime\) ist eine Zeichnung von \(G - y\) mit x ersetzt durch \(v_{xy}\).

Sei \(f_i\) das Gebiet von \(\tilde{G}^\prime\) mit Rand \(P_i, x_i v_{xy} x_{i + 1}\) wofür \(f_i \subseteq f\) gilt. Jetzt zeigen wir, dass \(Y \subseteq V(P_i)\) für ein bestimmtes i. Angenommen, dies ist nicht wahr. Dann gibt es ein i, dass es Nachbarn von y sowohl in \(\mathring{P}_i\) als auch \(C - P_i\) gibt. Aber dann ist \(K_{3,3}\) ein Minor. Widerspruch.

Also bleiben als Kandidatnachbarn von y nur \(x_i, i = 1, \dots, k \Rightarrow Y \subseteq X\). Ist \(|Y| \geq 3\), haben wir \(K_5\) als Minor, Widerspruch.

Also ist \(|Y| \leq 2\) und da G 3-zshgd ist auch \(|Y| \geq 2\). Zudem gilt \[ |Y \cap \{x_i, x_{i + 1}\} | \leq 1 \] Dann ist \(K_{3,3}\) erneut ein Minor. Also \(Y \subseteq V(P)\) und damit ist G einbettbar.

Dualität und plättbare Graphen

Definition 11.26

Ein ebener Multigraph ist ein ebener Graph bis auf Bedingung (ii), dass verschiedenen Kanten auch verschiedene Endpunkte haben müssen.

Der dualer ebener Multigraph \(G^*\) eines ebenen Multigraphs hat als Knotenmenge \(V(G^*)= F(G)\), eine Kante zwischen zwei Knoten wenn die Gebieten von G aneinander grenzen als Gebiete.

Satz 11.27 (Whintey, 1933)

Ein Graph ist genau dann plättbar, wenn ein zu ihm dualer Multigraph existiert.

Siehe auch: Dualer graph