Binary file planarity/term_paper.pdf has changed

--- a/planarity/term_paper.tex	Sun Jul 15 22:19:42 2012 +0200
+++ b/planarity/term_paper.tex	Sun Jul 15 22:47:56 2012 +0200
@@ -37,20 +37,21 @@
 \newcommand{\R}       {\mathbb{R}}          % reelle Zahlen
 \newcommand{\Oh}      {\mathcal{O}}         % O-Notation (Landau-Symbole)
 
+
 \begin{document}
 
 \maketitle
 
 \begin{abstract}
-Der Test auf Planarität eines Graphen hat bedeutende Konsequenzen für Visualisierung und Graphalgorithmen. Ich definiere das Problem, stelle mit dem Satz von Kuratowski eine bekannte Charakterisierung vor und erarbeite eine weniger Bekannte Lösung des Problems anhand der Tiefensuche, das Links-Rechts-Planaritätskriterium.
+Der Test auf Planarität eines Graphen hat bedeutende Konsequenzen für Visualisierung und Graphalgorithmen. Ich definiere das Problem, stelle mit dem Satz von Kuratowski eine bekannte Charakterisierung vor und erarbeite eine weniger bekannte Lösung des Problems anhand der Tiefensuche, das Links-Rechts-Planaritätskriterium.
 \end{abstract}
 
 \newpage
 
 \section{Planarität}
-Ein \emph{Graph} $G = (V, E)$ ist ein Tupel der endlichen \emph{Knotenmenge} $V$ und \emph{Kantenmenge} $E$ aus Paaren von Knoten $(u, v)$. Im Weiteren werden nur \emph{einfache} Graphen ohne Schleifen, also Kanten mit selben Anfangs- und Endknoten oder Mehrfachkanten betrachtet, da diese keinen Einfluss auf die Planarität eines Graphen haben. Außerdem bezeichnet $n = |V|$ und $m = |E|$.
+Ein \emph{Graph} $G = (V, E)$ ist ein Tupel der endlichen \emph{Knotenmenge} $V$ und \emph{Kantenmenge} $E$ aus Paaren von Knoten $(u, v)$. Im Weiteren werden nur \emph{einfache} Graphen ohne Mehrfachkanten oder Schleifen, also Kanten mit selben Anfangs- und Endknoten betrachtet, da diese keinen Einfluss auf die Planarität eines Graphen haben. Außerdem bezeichnet $n = |V|$ und $m = |E|$.
 
-Eine \emph{Zeichnung} eines Graphen ordnet jedem Knoten Koordinaten auf einer Ebene und jeder kannte eine Kurve zwischen ihren Endknoten zu. Eine Zeichnung heißt \emph{planar} wenn sich keine Kanten schneiden. Zwei Zeichnungen heißen \emph{äquivalent}, wenn ihre Reihenfolge der Kanten um jeden Knoten gleich ist. Diese Äquivalenzklasse von Zeichnungen wird \emph{Einbettung} genannt und ist planar falls eine ihrer Zeichnungen planar ist.
+Eine \emph{Zeichnung} eines Graphen ordnet jedem Knoten Koordinaten auf einer Ebene und jeder Kante eine Kurve zwischen ihren Endknoten zu. Eine Zeichnung heißt \emph{planar} wenn sich keine Kanten schneiden. Zwei Zeichnungen heißen \emph{äquivalent}, wenn ihre Reihenfolge der Kanten um jeden Knoten gleich ist. Diese Äquivalenzklasse von Zeichnungen wird \emph{Einbettung} genannt und ist planar falls eine ihrer Zeichnungen planar ist.
 
 \begin{definition}
 Ein Graph heißt \emph{planar}, wenn für ihn eine planare Zeichnung existiert.
@@ -73,7 +74,7 @@
 Dieses Lemma stellt außerdem für planare Graphen einen linearen Zusammenhang zwischen Kanten und Knoten her, es gilt $m \in \Oh(n)$, während für allgemeine Graphen nur $m \in \Oh(n^2)$ gilt.
 
 \subsection{Die Sätze von Kuratowski und Wagner}
-In den 1930er Jahren haben Kuratowski\cite{Kur30} und Wagner\cite{Wag37} erste Charakterisierungen für planare Graphen gefunden. Diese Charakterisierungen basieren auf \emph{Unterteilungen} und \emph{Minoren}.Eine Unterteilung eines Graphen entsteht durch beliebig häufiges Einfügen von neuen Knoten auf vorhandenen Kanten. Ein Graph ist Minor eines anderen Graphen, wenn er sich durch Löschen von Knoten oder Kanten oder Kantenkontraktion gewinnen lässt.
+In den 1930er Jahren haben Kuratowski\cite{Kur30} und Wagner\cite{Wag37} erste Charakterisierungen für planare Graphen gefunden. Diese Charakterisierungen basieren auf \emph{Unterteilungen} und \emph{Minoren}. Eine Unterteilung eines Graphen entsteht durch beliebig häufiges Einfügen von neuen Knoten auf vorhandenen Kanten. Ein Graph ist Minor eines anderen Graphen, wenn er sich durch Löschen von Knoten oder Kanten oder Kantenkontraktion gewinnen lässt.
 
 \begin{theorem}
 Ein Graph ist genau dann planar wenn er keinen Teilgraphen (\emph{Kuratowski}) enthält, der eine Unterteilung von $K_5$ oder $K_{3,3}$ ist und er nicht Minor (\emph{Wagner}) eines dieser Graphen ist.
@@ -115,19 +116,19 @@
 \end{figure}
 
 \subsection{Geschichte der Planaritätsprüfung}
-Während die Formulierung des Problems einfach ist und Kuratowski und Wagner in den dreißiger Jahren eine charakterisierung für planare Graphen finden konnten, war längere Zeit kein effizienter Algorithmus zum Testen auf Planarität bekannt. Erst 1961 fangen Auslander und Parter\cite{AP61} einen Polynomialzeitalgorithmus basierend auf der Unterteilung von Kreisen. 1974 stellten Hopcroft und Tarjan\cite{HT74} einen ersten Linearzeitalgorithmus vor, der auf dem Betrachten einzelner Pfade im Graphen basiert. Diese Algorithmen basieren jedoch meist auf komplexen Datenstrukturen und sind reltiv schwer zu implementieren.
+Während die Formulierung des Problems einfach ist und Kuratowski und Wagner in den dreißiger Jahren eine Charakterisierung für planare Graphen finden konnten, war längere Zeit kein effizienter Algorithmus zum Testen auf Planarität bekannt. Erst 1961 fanden Auslander und Parter\cite{AP61} einen Polynomialzeitalgorithmus basierend auf der Unterteilung von Kreisen. 1974 stellten Hopcroft und Tarjan\cite{HT74} einen ersten Linearzeitalgorithmus vor, der auf dem Betrachten einzelner Pfade im Graphen aufbaut. Diese Algorithmen verwenden jedoch meist komplexe Datenstrukturen und sind relativ schwer zu implementieren.
 
-Im folgenden soll das \emph{LR-Planaritätskriterium} vorgestellt werden, das auf der Tiefensuche basiert und ursprünglich von de Fraysseix, Ossona de Mendez und Rosenstiehl 2006\cite{FMR06} veröffentlicht und 2009 von Brandes\cite{Bra09} näher beschrieben wurde.
+Im Folgenden soll das \emph{LR-Planaritätskriterium} vorgestellt werden, das auf der Tiefensuche basiert und ursprünglich von de Fraysseix, Ossona de Mendez und Rosenstiehl 2006\cite{FMR06} veröffentlicht und 2009 von Brandes\cite{Bra09} näher beschrieben wurde.
 
 \section{Das LR-Planaritätskriterium}
 Die Planarität eines Graphen wird durch die Beschaffenheit seiner Kreise bestimmt. Während zyklenfreie Graphen immer planar sind, können sich Kreise schneiden. Zyklen schließen eine Fläche auf der Ebene. Um Überschneidungen zu vermeiden müssen Teilgraphen in Berührung zu diesem Kreis entweder komplett innerhalb oder komplett außerhalb gezeichnet werden.
 
-Weiterhin existieren genau zwei Möglichkeiten einen Kreis auf der Ebene zu zeichnen, im und gegen den Uhrzeigersinn. Entscheidet man sich bei einem Kreis für eine Orientierung werden so möglicherweise Beschränkungen für alle anderen Kreise erzeugt, da sich Regeln für die planare Einbettung ergeben. Das Testen auf Planarität soll mithilfe der \emph{LR-Zerlegung} zurückgeführt werden auf den Test, ob sich diese Regeln widersprechen.
+Weiterhin existieren genau zwei Möglichkeiten einen Kreis auf der Ebene zu zeichnen, im und gegen den Uhrzeigersinn. Entscheidet man sich bei einem Kreis für eine Orientierung werden so möglicherweise Beschränkungen für alle anderen Kreise erzeugt, da sich Regeln für die planare Einbettung ergeben. Das Testen auf Planarität soll mit Hilfe der \emph{LR-Zerlegung} zurückgeführt werden auf den Test, ob sich diese Regeln widersprechen.
 
-In einem Graphen existieren jedoch potentiell exponentiell viele einfache Kreise. Um diese Zahl einzuschränken wird eine \emph{DFS-Orientierung} des Graphen erzeugt und es wird gezeigt dass eine Betrachtung der Rückwärtskanten eine Aussage über Planarität zulässt.
+In einem Graphen existieren jedoch potentiell exponentiell viele einfache Kreise. Um diese Zahl einzuschränken wird eine \emph{DFS-Orientierung} des Graphen erzeugt und es wird gezeigt, dass allein eine Betrachtung der Rückwärtskanten eine Aussage über Planarität zulässt.
 
 \subsection{Tiefensuche}
-Eine Tiefensuche auf einem ungerichteten Graphen $G = (V, E)$ erzeugt eine \emph{DFS-Orientierung} $G = (G, V)$ wobei jeder Kante die Richtung zugewiesen wird, in der sie durchlaufen wird. Die Tiefensuche ergibt außerdem eine Partition $\vec{E} = T \uplus B$ der Kanten in Baumkanten $T$ und Rückwärtskanten $B$. Der Graph $(V, T)$ ist ein maximal zyklenfreier Graph, das hinzufügen einer beliebigen Kante aus B erzeugt einen Zyklus. 
+Eine Tiefensuche auf einem ungerichteten Graphen $G = (V, E)$ erzeugt eine \emph{DFS-Orientierung} $G = (G, V)$ wobei jeder Kante die Richtung zugewiesen wird, in der sie durchlaufen wird. Die Tiefensuche ergibt außerdem eine Partition $E = T \uplus B$ der Kanten in Baumkanten $T$ und Rückwärtskanten $B$. Der Graph $(V, T)$ ist maximal zyklenfrei, das Hinzufügen einer beliebigen Kante aus B erzeugt einen Zyklus. 
 
 \begin{figure}[htb]
 	\centering
@@ -174,7 +175,7 @@
 \end{tikzpicture}	
 	}
 	\hspace*{\fill}	
-	\caption{Planarer Beispielgraph (aus \cite{Bra09}).}
+	\caption{Planarer Beispielgraph (aus \cite{Bra09})}
 	\label{dfs:graph}	
 \end{figure}
 
@@ -244,7 +245,7 @@
 In einer planaren Zeichnung eines DFS-orientierten Graphen sind zwei Kreise mit gemeinsamem Baumpfad genau dann \emph{verschachtelt}, wenn sie gleich orientiert sind.
 \end{observation}
 
-Diese Beobachtung macht jedoch keine Aussage darüber welcher Kreis der Innere ist. Hierfür wird angenommen, dass die Wurzel der DFS-Orientierung immer an der äußeren Fläche der Zeichnung liegt. Da ein Kreis immer durch genau eine Rückwärtskante induziert wird, können zwei solche Kreise $c_1$ und $c_2$ mit ihren jeweiligen Rückwärtskanten $b_1$ und $b_2$ identifiziert werden. Nimmt man außerdem an, dass $lowpt(b_1) < lowpt(b_2)$, dann muss $c_2$ innerhalb von $c_1$ liegen. Da die Lowpoints unterschiedlich sind, muss es einen Baumpfad geben, der sie verbindet. Dieser Pfad kann aber nicht Teil des inneren Kreises sein, da die Wurzel der DFS-Orientierung die äußere Fläche berühren soll.
+Diese Beobachtung macht jedoch keine Aussage darüber, welcher Kreis der Innere ist. Hierfür wird angenommen, dass die Wurzel der DFS-Orientierung immer an der äußeren Fläche der Zeichnung liegt. Da ein Kreis immer durch genau eine Rückwärtskante induziert wird, können zwei solche Kreise $c_1$ und $c_2$ mit ihren jeweiligen Rückwärtskanten $b_1$ und $b_2$ identifiziert werden. Nimmt man außerdem an, dass $lowpt(b_1) < lowpt(b_2)$, dann muss $c_2$ innerhalb von $c_1$ liegen. Da die Lowpoints unterschiedlich sind, muss es einen Baumpfad geben, der sie verbindet. Dieser Pfad kann aber nicht Teil des inneren Kreises sein, da die Wurzel der DFS-Orientierung die äußere Fläche berühren soll.
 
 \begin{observation}
 In einer planaren Zeichnung eines DFS-orientierten Graphen bei dem die Wurzel die äußere Fläche berührt werden Kreise die sich Baumpfade teilen anhand ihrer Lowpoints verschachtelt.
@@ -272,7 +273,7 @@
     \foreach \source/ \dest in {k/c, k/i, j/a, g/d, n/l}
         \path[right edge] (\source) -- (\dest);
 \end{tikzpicture}
-	\caption{LR-Zerlegung des Beispielgraphen aus Abb.\ref{dfs:graph}}
+	\caption{LR-Zerlegung des Beispielgraphen aus Abb. \ref{dfs:graph}}
 	\label{lr:graph}	
 \end{figure}
 
@@ -299,9 +300,9 @@
 
 Da planare Einbettungen durch ihre Kantenreihenfolge um Knoten definiert sind, muss aus der LR-Zerlegung eine solche Reihenfolge konstruiert werden. Hierbei gilt, dass bei einer Gabelung linksorientierte Kanten im Uhrzeigersinn vor rechtsorientierten Kanten angeordnet werden müssen. Linke (rechte) Kanten müssen außerdem von innen nach außen (von außen nach innen) um ihren Knoten angeordnet werden.
 
-Diese Orientierung ist bisher jedoch nur für Rückwärtskanten bekannt und muss auf Baumkanten erweitert werden. Dafür ist der Begriff der \emph{ausgerichteten} LR-Zerlegung nötig. Eine LR-Zerlegung heißt ausgerichtet, wenn alle Rückwärtskanten einer Kante $e$, die in $lowpt(e)$ enden, zur selben Seite gehören. Jede LR-Zerlegung kann ausgerichtet werden, da für alle Kanten die in $lowpt(e)$ enden die selben Bedingungen gelten. Hat eine Baumkante Rückwärtskanten, dann wird sie der Seite derjenigen Kante zugewiesen, die den höchsten Rückkehrpunkt (analog zum Lowpoint) besitzt. Andererseits kann die Seite beliebig gewählt werden.
+Diese Orientierung ist bisher jedoch nur für Rückwärtskanten bekannt und muss auf Baumkanten erweitert werden. Dafür ist der Begriff der ausgerichteten LR-Zerlegung nötig. Eine LR-Zerlegung heißt \emph{ausgerichtet}, wenn alle Rückwärtskanten einer Kante $e$, die in $lowpt(e)$ enden, zur selben Seite gehören. Jede LR-Zerlegung kann ausgerichtet werden, da für alle Kanten die in $lowpt(e)$ enden die selben Bedingungen gelten. Hat eine Baumkante Rückwärtskanten, dann wird sie der Seite derjenigen Kante zugewiesen, die den höchsten Rückkehrpunkt (analog zum Lowpoint) besitzt. Andererseits kann die Seite beliebig gewählt werden.
 
-Für Baumkanten und Rückwärtskanten muss nun eine Verschachtelungsreihenfolge $\prec$ festgelegt werden. Hierfür wird angenommen, dass alle Kanten rechte Kanten sind und wir betrachten eine Gabelung aus Knoten $v$ und Kanten $e_1$ und $e_2$, die $v$ verlassen. Wenn beide Rückwärtskanten haben deren Lowpoint tiefer als $v$ liegt, dann dann ist $v$ Gabelungspunkt für zwei Kreise die sich die Baumkante $(u, v)$ teilen. Da beide Kreise rechtsorientiert sind müssen sie richtig verschachtelt werden. Da die Quelle der Tiefensuche an der äußeren Fläche liegt, müssen wir $e_1 \prec e_2$ genau dann annehmen, wenn $lowpt(e_1) < lowpt(e_2)$. Haben beide den selben Lowpoint, jedoch $e_2$ noch eine höhere Rückwärtskante und $e_1$ nicht, so besitzt $e_2$ eine Sehne und wir nehmen $e_1 \prec e_2$ an, da zusätzliche Kreise in $e_2$ immer innerhalb von durch $e_1$ definierten Kreises liegen müssen. Wenn sowohl $e_1$ als auch $e_2$ eine Sehne haben wird die Reihenfolge beliebig gewählt, da beide in verschiedenen Klassen gezeichnet werden müssen um überschneidungsfrei sein zu können.
+Für Baumkanten und Rückwärtskanten muss nun eine Verschachtelungsreihenfolge $\prec$ festgelegt werden. Hierfür wird angenommen, dass alle Kanten rechte Kanten sind und wir betrachten eine Gabelung aus Knoten $v$ und Kanten $e_1$ und $e_2$, die $v$ verlassen. Wenn beide Rückwärtskanten haben deren Lowpoint tiefer als $v$ liegen, dann ist $v$ Gabelungspunkt für zwei Kreise, die sich die Baumkante $(u, v)$ teilen. Da beide Kreise rechtsorientiert sind müssen sie richtig verschachtelt werden. Da die Wurzel der Tiefensuche an der äußeren Fläche liegt, müssen wir $e_1 \prec e_2$ genau dann annehmen, wenn $lowpt(e_1) < lowpt(e_2)$. Haben beide den selben Lowpoint, jedoch $e_2$ noch eine höhere Rückwärtskante und $e_1$ nicht, so besitzt $e_2$ eine Sehne und wir nehmen $e_1 \prec e_2$ an, da zusätzliche Kreise in $e_2$ immer innerhalb des durch $e_1$ definierten Kreises liegen müssen. Wenn sowohl $e_1$ als auch $e_2$ eine Sehne haben wird die Reihenfolge beliebig gewählt, da beide in verschiedenen Klassen gezeichnet werden müssen um überschneidungsfrei sein zu können.
 
 \begin{definition}[LR-Ordnung]
 Zu einer gegebenen LR-Parition seien $e_1^L \prec \hdots \prec e_l^L$ die linksorientierten und $e_1^R \prec \hdots \prec e_r^R$ die rechtsorientierten ausgehenden Kanten von $v$. Wenn $v$ nicht die Wurzel ist sei $u$ seine Quelle. Die \emph{LR-Ordnung} im Uhrzeigersinn um $v$ ist dann gegeben durch: