notes/school/di-ma/20181121_2-planare_graphen.md

---
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$}
$$