--- title: Planare Graphen date: 2018-11-21 --- **Frage**: Welche Graphen kann man besonders "schön" zeichnen? Genauer: Welche Graphen kann man so zeichnen, dass sich keine Kanten schneiden? # Definition (Planarer Graph) Ein Graph $G=(V,E)$ heißt planar, falls er so in die Ebene eingebettet werden kann, dass sich keine Kanten schneiden. **Beispiel**: i) $K_3$ ![$K_3$](20181121_2-k3.png) ist planar i) $K_4$ ![$K_4$](20181121_2-k4.png) ist planar i) $K_5$ ![$K_5$](20181121_2-k5.png) ist nicht planar **Bemerkungen**: i) Planar ist Eigenschaft des Graphen, nicht der Einbettung (Auch planare Graphen können nicht planar Gezeichnet werden) i) Zu zeigen, dass ein Graph **nicht** planar ist, ist (erstmal) nicht so einfach **Weitere Beispiele**: Vollständige bipartite Graphen $K_{n,m}=(V,E)$ bestehen aus 2 disjunkten Knotenmengen $V_1, V_2$ mit $|V_1| = n, |V_2| = m$ und $V = V_1 \biguplus V_2$ wobei $E = \{ \{u,v\} | u \in V_1, v \in V_2 \}$ i) $K_{2,3}$: ![$K_{2,3}$](20181121_2-k23.png) ist planar ($\{1,4\}$ und $\{1,5\}$ außen zeichnen) i) $K_{3,3}$: ![$K_{3,3}$](20181121_2-k33.png) ist nicht planar Wir betrachten als nächstes die Gebiete/Flächen in die die planare Einbettung eines planaren Graphen die Ebene unterteilt. **Beispiel**: i) $K_3$ unterteilt die Ebene in 2 Flächen (eine innere und eine äußere) i) $K_4$ unterteilt die Ebene in 4 Flächen i) $K_{2,3}$ unterteilt die Ebene in 3 Flächen Die Anzahl der Flächen/Gebiete ist unabhängig von der genauen planaren Einbettung. # Satz (Eulersche Polyederformel) Sei $G=(V,E)$ ein zusammenhängender planarer Graph. Sei $f$ die Anzahl der Gebiete einer planaren Einbettung von $G$. Dann gilt $f = |E| - |V| + 2$ # Beweis (Eulersche Polyederformel) (per Induktion über $|E|$) **Induktionsanfang**: Da $G$ zusammenhängend gilt $|E| \geq |V| - 1$. Daher Induktionsanfang für $|E| = |V| - 1$. Damit ist $G$ ein Baum und die Anzahl der Gebiete $f$ ist 1 (1 äußeres, 0 innere). Es gilt $$ \begin{align*} 1 = f &= |E| - |V| + 2 \\ &= (|V| - 1) - |V| + 2 = 1 \end{align*} $$ **Induktionsschritt**: Sei nun $|E| > |V| - 1$. Dann enthält $G$ einen Kreis und sei $c = \{u,v\} \in E$ eine Kreiskante. Betrachte $G' = (V, E \setminus \{c\})$. Dann gilt (nach Induktionsanfang): i) $f' = |E'| - |V| + 2 = (|E| - 1) - |V| + 2$ i) $f' = f - 1$ da durch Wegnahme von $c$ zwei Gebiete von $G$ zusammenfallen $\Rightarrow$ $f - 1 = f' = |E| - |V| + 1$ $\Rightarrow$ $f = |E| - |V| + 2$ $$ \tag*{$\Box$} $$ Verallgemeinerung des obigen Satzes: # Satz Sei $G=(V,E)$ ein planarer Graph mit $k$ Zusammenhangskomponenten. Sei $f$ die Anzahl der Gebiete eines planaren Diagrammes, dann gilt $$ f = |E| - |V| + k + 1 $$ # Beweis Seien $G_i = (V_i,E_i)$, $i \in \{1,...,k\}$ die Zusammenhangskomponenten von $G$. Dann gilt $$ \begin{align*} V &= \biguplus\limits_{i \in \{1,...,k\}} V_i \\ E &= \biguplus\limits_{i \in \{1,...,k\}} E_i \end{align*} $$ Sei $f_i$ die Anzahl der Gebiete von $G_i$, dann gilt i) $f_i = |E_i| - |V_i| + 2$ (Satz von oben, Zusammenhangskomponenten sind zusammenhängend) i) $f = \sum\limits_{i=1}^k f_i - (k-1)$, da wir in $\sum\limits_{i=1}^k f_i$ das äußere Gebiet $k$-mal gezählt haben. $$ \begin{align*} \Rightarrow f &= \sum\limits_{i=1}^k (|E_i| - |V_i| - 2) - (k-1) \\ &= \sum\limits_{i=1}^k |E_i| - \sum\limits_{i=1}^k |V_i| + 2k -(k-1) \\ &= |E| - |V| + k + 1 \end{align*} $$ $$ \tag*{$\Box$} $$ Der folgende Satz zeigt, dass planare Graphen für gegebenes $|V|$ nicht zu viele Kanten haben können. # Satz Sei $G=(V,E)$ planar mit $|V| \geq 3$. Dann gilt $|E| \leq 3 |V| - 6$ ## Beispiel $K_5$ hat $|V|=5$ Knoten und $|E|=\binom{5}{2} = \frac{5\cdot 4}{2} = 10$ Kanten und es gilt $3 * |V| - 6 = 9 < 10 = |E|$ $\Rightarrow$ $K_5$ ist nicht planar # Beweis Sei ohne Einschränkung $G=(V,E)$ zusammenhängend. Seien $R_1,...,R_f$ die Gebiete eines planaren Diagrammes von $G$ und $E = \{ e_1,...e_m \}$ die Kanten. Betrachte folgende Matrix: $$ A = a_{i,j} = \begin{cases} 1 & \text{falls } e_i \text{ das Gebiet } R_i \text{ berandet} \\ 0 & \text{sonst} \end{cases} $$ Dann gilt i) Zeilensummen sind $\leq 2$ i) Spaltensummen sind $\geq 3$ Doppeltes Abzählen liefert $ef \leq 2 |E|$ $\Rightarrow$ $f = \frac{2}{3} |E|$ und da $f = |E| -|V|+2$ gibt, folgt $\Rightarrow$ $|E|-|V|+2 \leq \frac{2}{3} |E|$ $\Rightarrow$ $\frac{1}{3}|E| \leq |V|-2$ $\Rightarrow$ $|E| \leq 3 |V| -6$ $$ \tag*{$\Box$} $$ Für $K_{3,3}$ reicht der Satz nicht aus, denn $|V| = 6$ und $|E|=9$ und $3|V|-6=12>9=|E|$. Aus dem Satz folgt nicht, dass $K_{3,3}$ nicht planar ist. Aber es stimmt trotzdem. # Erweiterung des Satzes Sei $G$ ein planarer Graph, der keinen Kreis der Länge 3 enthält. Dann gilt $$ |R| \leq 2|V| -4 $$ In diesem Fall wird dieses Gebiet von mindestens 4 Kanten umrandet. Der Beweis folgt dann analog zu oben. $K_{3,3}$ enthält keinen Kreis der Länge 3 und $2|V| - 4 = 2 \cdot 6 - 4 = 8 < 9 = |E|$. $\Rightarrow$ $K_{3,3}$ ist nicht planar. # Korollar $K_5$ und $K_{3,3}$ sind nicht planar. a) Im wesentlichen sind das alle. Klar ist, dass jeder Graph $G=(V,E)$, der $K_5$ oder $K_{3,3}$ als Teilgraph enthält nicht planar ist. Denn jeder Teilgraph eines planaren Graphen ist planar a) **Unterteilungen** eines Graphen $G=(V,E)$ entstehen durch ersetzen einer Kante durch einen Pfad (und entsprechend Einfügen von neuen Knoten). **Beispiel**: $K_4$ ![$K_4$](20181121_2-k4_unterteilung.png) Unterteilungen des $K_5$ und $K_{3,3}$ sind nicht planar. **Allgemein**: Unterteilungen von nicht planaren Graphen sind nicht planar (und umgekehrt). Diese beiden Punkte a) und b) zusammen mit $K_5$ und $K_{3,3}$ nicht planar charakterisieren alle nicht planaren Graphen (ohne Beweis) # Satz (Nicht-planar) Sei $G=(V,E)$ ein Graph. G ist nicht-planar genau dann, wenn G eine Unterteilung des $K_5$ oder $K_{3,3}$ als Teilgraph enthält "$\Leftarrow$" haben wir gezeigt "$\Rightarrow$" schwer ## Bemerkung Es gibt Algorithmen, die in Laufzeit $O(|V|+|E|)§ entscheiden, ob $G=(V,E)$ planar ist, oder nicht, und die, falls $G$ planar ist, ein planares Diagramm von $G$ berechnen Das folgende Korollar werden wir später nutzen ## Korollar $Sei $G=(V,E)$ ein planarer zusammenhängender Graph. Dann gibt es ein $v \in V$ mit $deg(v) \leq 5$ ## Beweis Für $|V| < 3$ ist diese Aussage trivial. Sei also $|V| \geq 3$ und $d = \min\limits_{v \in V} deg(v)$. Dann gilt $$ \begin{align*} d * |V| \leq \sum\limits_{v \in V} deg(v) = 2*|E| &\leq 2 * (3 * |V| - 6) \\ &= 6 * |V| - 12 \\ &< 6*|V| \end{align*} $$ $\Rightarrow$ $d < 6$ $\Rightarrow$ $\exists v \in V: deg(v) < 6$ $$ \tag*{$\Box$} $$