--- a/planarity/presentation.tex	Sun Jul 15 14:39:22 2012 +0200
+++ b/planarity/presentation.tex	Sun Jul 15 22:15:04 2012 +0200
@@ -594,7 +594,7 @@
 	\begin{definition}
 		Seien \alert{$e_1^L,\ldots,e_l^L$} die linken ausgehenden Baumkanten und \alert{$e_1^R,\ldots,e_r^R$} die rechten ausgehenden Baumkanten eines Knotens $v$ und $u$ sein Elternknoten. Dann ist die \alert{LR-Ordnung} im Uhrzeigersinn
 		\begin{align*}
-			&(u,v),\\
+			&(u, v),\\
 			&L(e_l^L),e_l^L,R(e_l^L),\ldots,R(e_1^L),\\
 			&L(e_1^R),\ldots,L(e_r^R),e_r^R,R(e_r^R)
 		\end{align*}

--- a/planarity/term_paper.bib	Sun Jul 15 14:39:22 2012 +0200
+++ b/planarity/term_paper.bib	Sun Jul 15 22:15:04 2012 +0200
@@ -3,7 +3,7 @@
 	title =		{The left-right planarity test},
 	year = 		{2009},
 	note = 		{Manuscript submitted for publication},
-	ee = 		{http://www.inf.uni-konstanz.de/algo/publications/b-lrpt-sub.pdf},
+	ee = 		{http://www.inf.uni-konstanz.de/algo/publications/b-lrpt-sub.pdf}
 }
 
 @incollection{Pat13,
@@ -13,7 +13,7 @@
 	title =		{Planarity Testing and Embedding},
 	year = 		{2013},
 	publisher = 	{CRC Press},
-	ee = 		{http://www.cs.brown.edu/~rt/gdhandbook/},
+	ee = 		{http://www.cs.brown.edu/~rt/gdhandbook/}
 }
 
 @article{Kur30,
@@ -51,7 +51,6 @@
     year = {1961}
 }
 
-
 @article{HT74,
  author = {Hopcroft, John and Tarjan, Robert},
  title = {Efficient Planarity Testing},
@@ -68,5 +67,19 @@
  doi = {10.1145/321850.321852},
  acmid = {321852},
  publisher = {ACM},
- address = {New York, NY, USA},
+ address = {New York, NY, USA}
 } 
+
+@article{FMR06,
+  author    = {Hubert de Fraysseix and
+               Patrice Ossona de Mendez and
+               Pierre Rosenstiehl},
+  title     = {Tr{\'e}maux Trees and Planarity},
+  journal   = {Int. J. Found. Comput. Sci.},
+  volume    = {17},
+  number    = {5},
+  year      = {2006},
+  pages     = {1017-1030},
+  ee        = {http://dx.doi.org/10.1142/S0129054106004248},
+  bibsource = {DBLP, http://dblp.uni-trier.de}
+}

--- a/planarity/term_paper.tex	Sun Jul 15 14:39:22 2012 +0200
+++ b/planarity/term_paper.tex	Sun Jul 15 22:15:04 2012 +0200
@@ -5,52 +5,448 @@
 \usepackage[utf8]{inputenc}
 \usepackage{amsmath}
 \usepackage[pdftex]{hyperref}
+\usepackage{tikz}
+\usepackage{subfig}
+\usepackage{wrapfig}
 
-\ifpdf
-	\usepackage[pdftex]{graphicx}
-	\DeclareGraphicsExtensions{.pdf, .png, .jpg}
-\else
-	\usepackage[dvips]{graphicx}
-	\DeclareGraphicsExtensions{.eps}
-\fi
+\usetikzlibrary{shapes.geometric}
+\pgfdeclarelayer{background}
+\pgfdeclarelayer{midground}
+\pgfsetlayers{background,midground,main}
+\tikzstyle{vertex}=[circle,draw,fill=blue!25,minimum size=12pt,inner sep=0pt]
+\tikzstyle{selected vertex} = [vertex, fill=red!50]
+\tikzstyle{very small vertex} = [vertex, minimum size=4pt]
+\tikzstyle{small vertex} = [vertex, minimum size=8pt]
+\tikzstyle{edge} = [draw,thick,-]
+\tikzstyle{tree edge} = [draw,very thick,->]
+\tikzstyle{left edge} = [draw,thick,->, blue]
+\tikzstyle{right edge} = [draw,thick,->, red]
+\tikzstyle{back edge} = [draw,dashed,arrows={-latex}]
+\tikzstyle{selected edge} = [draw,line width=5pt,-,red!50]
+
 
 \title{Testen eines Graphen auf Planarität}
 \author{Markus Kaiser}
 \institute{Technische Universit\"at M\"unchen\\
 \email{markus.kaiser@in.tum.de}}
 
-\newtheorem{hypothesis}{Hypothese}
+\newtheorem{observation}{Beobachtung}
+
+\newcommand{\N}       {\mathbb{N}}          % natürliche Zahlen
+\newcommand{\Z}       {\mathbb{Z}}          % ganze Zahlen
+\newcommand{\R}       {\mathbb{R}}          % reelle Zahlen
+\newcommand{\Oh}      {\mathcal{O}}         % O-Notation (Landau-Symbole)
 
 \begin{document}
 
 \maketitle
 
 \begin{abstract}
-  Hier die Zusammenfassung eintragen
+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{Vorwort}
-Siehe Einleitung von \cite{Pat13}
-
 \section{Planarität}
-Bla bla Definition, Charakterisierung von \cite{Kur30} und \cite{Wag37}, einfachere LR-Charakterisierung.
+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|$.
+
+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.
+
+\begin{definition}
+Ein Graph heißt \emph{planar}, wenn für ihn eine planare Zeichnung existiert.
+\end{definition}
+
+Zeichnungen unterteilen die Ebene in \emph{Flächen} mit $f$ als der Anzahl der Flächen. Es existieren abgeschlossene \emph{innere} Flächen und genau eine offene \emph{äußere} Fläche. Der eulersche Polyedersatz stellt einen Zusammenhang her zwischen der Anzahl Knoten, Kanten und Flächen in einer planaren Zeichnung.
+
+\begin{theorem}[Eulerscher Polyersatz]
+Für zusammenhängende planare Graphen gilt in jeder Zeichnung $n - m + f = 2$
+\end{theorem}
+
+Daraus ergibt sich direkt ein Kriterium zur Planaritätsprüfung anhand der Kantenanzahl.
+
+\begin{lemma}
+Für jeden planaren Graphen gilt $m \leq 3n - 6$
+\end{lemma}
+\begin{proof}
+Jede Kante kann maximal zwei Flächen begrenzen. Außerdem wird eine Fläche von mindestens drei Kanten begrenzt. Daraus ergibt sich $f \leq \frac{2m}{3}$ und $m \leq 3n - 6$.
+\end{proof}
+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.
+
+\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.
+\end{theorem}
+
+$K_5$ und $K_{3,3}$ sind also die kleinstmöglichen nicht planaren Graphen. Dieses Kriterium ist einfach zu verstehen, würde aber bei direkter Anwendung zu mindestens exponentiellen Algorithmen führen und ist deswegen zum Testen auf Planarität ungeeignet.
 
-Geschichte der Algorithmen Auslander Parter\cite{AP61}, Hopcroft\cite{HT74}.
-Direkte Anwendung von Kuratowski oder Wagner führt zu schlechten Algorithmen, danach Auslander Parter polynomiell und Hopcroft und Tarjan linear.
-Blubberwurst\cite{Bra09}
+\begin{figure}[htb]
+	\centering
+	\hspace*{\fill}
+	\subfloat[$K_5$]{
+\begin{tikzpicture}      
+  \foreach \x/\y in {18/a,90/b,162/c,234/d,306/e} {
+     \node[small vertex] (\y) at (\x:1.1cm) {};
+  }
+ 
+ \foreach \x/\y in {a/b,a/c,a/d,a/e,
+                 b/c,b/d,b/e,
+                 c/d,c/e,
+                 d/e} {
+     \draw[edge] (\x) -- (\y);
+ }
+\end{tikzpicture}
+	}
+	\hspace*{\fill}
+	\subfloat[$K_{3,3}$]{
+	\begin{tikzpicture}[auto]
+    \foreach \pos/ \name in {{(0,1)/a}, {(0,2)/b}, {(0,3)/c},{(1.5,1)/d},{(1.5,2)/e},{(1.5,3)/f}}
+        \node[small vertex] (\name) at \pos {};
+        
+    \foreach \source/ \dest in {a/d, a/e, a/f,
+                                b/d, b/e, b/f,
+                                c/d, c/e, c/f}
+        \path[edge] (\source) -- (\dest);   
+	\end{tikzpicture}
+	}
+	\hspace*{\fill}
+	\caption{Minimal nicht planare Graphen $K_5$ und $K_{3,3}$.}
+\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.
+
+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}
-Wurst.
+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.
+
+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.
+
+\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. 
+
+\begin{figure}[htb]
+	\centering
+	\hspace*{\fill}
+	\subfloat[Beispielgraph]{
+\begin{tikzpicture}[scale=0.65]
+	\useasboundingbox (-4,0) rectangle (4,6);
+
+    \foreach \pos/\name in {{(0,1)/a},{(0,2)/b},{(1,3)/c},{(0.75,4)/d},{(-0.5,4.5)/e},
+                            {(-1.5,3.5)/f}, {(1.25,5.25)/g},
+                            {(0,5.5)/h}, {(2.5,6)/i}, {(4,5)/j},{(2.5,4.5)/k},
+                            {(-2,6)/l}, {(-2.5,5)/m}, {(-4,5)/n}}
+        \node[small vertex] (\name) at \pos {};
+        
+    
+    \foreach \source/ \dest in {a/b, b/c, c/d, d/e, e/f, e/g,
+                                e/h, h/i, i/j, j/k,
+                                h/l, l/m, m/n}
+        \path[edge] (\source) -- (\dest);     
+        
+    \foreach \source/ \dest in {f/b, k/c, k/i, j/a, g/d, m/e, n/l, n/a}
+        \path[edge] (\source) -- (\dest);
+\end{tikzpicture}
+	}
+	\centering
+	\hspace*{\fill}
+	\subfloat[DFS-Orientierung]{
+\begin{tikzpicture}[scale=0.65]
+	\useasboundingbox (-4,0) rectangle (4,6);
+
+    \foreach \pos/\name in {{(0,1)/a},{(0,2)/b},{(1,3)/c},{(0.75,4)/d},{(-0.5,4.5)/e},
+                            {(-1.5,3.5)/f}, {(1.25,5.25)/g},
+                            {(0,5.5)/h}, {(2.5,6)/i}, {(4,5)/j},{(2.5,4.5)/k},
+                            {(-2,6)/l}, {(-2.5,5)/m}, {(-4,5)/n}}
+        \node[small vertex] (\name) at \pos {};
+        
+    \foreach \source/ \dest in {a/b, b/c, c/d, d/e, e/f, e/g,
+                                e/h, h/i, i/j, j/k,
+                                h/l, l/m, m/n}
+        \path[tree edge] (\source) -- (\dest);      
+        
+    \foreach \source/ \dest in {f/b, k/c, k/i, j/a, g/d, m/e, n/l, n/a}
+        \path[back edge] (\source) -- (\dest);
+\end{tikzpicture}	
+	}
+	\hspace*{\fill}	
+	\caption{Planarer Beispielgraph (aus \cite{Bra09}).}
+	\label{dfs:graph}	
+\end{figure}
+
+\begin{lemma}
+Sei $G = (V, T \uplus B)$ ein DFS-orientierter Graph.
+\begin{enumerate}
+	\item Alle Kreise in G werden durch genau eine Rückswärtskante induziert.
+	\item Zwei Kreise sind entweder unabhängig oder teilen sich einen Pfad in $T$.
+\end{enumerate}
+\end{lemma}
+
+Teilen sich zwei Kreise einen Pfad in $T$, so ist ihr \emph{Gabelungspunkt} definiert als der letzte Knoten der Teil beider Kreise ist. Ihre \emph{Gabelung} bezeichnet die letzte gemeinsame Baumkante und die jeweils folgenden Kanten. Da Kreise nur durch Rückwärtskanten erzeugt werden, muss für jede dieser Gabelungen eine Verschachtelungsreihenfolge um ihren Gabelungspunkt gefunden werden.
+
+\begin{wrapfigure}{r}{0.4\textwidth}
+	\begin{tikzpicture}[auto, scale=0.5]
+	\useasboundingbox (-4, 1.5) rectangle (4, 9);	
+	
+	\node[small vertex] (u) at (0,4) {};
+	\node[small vertex] (v) at (0,6) {$v$};
+	\node[small vertex] (w) at (-2,8) {};	
+	\node[small vertex] (x) at (2,8) {};
+	\node[small vertex] (l) at (0,2) {};
+	
+	\path[edge] (u) -- (v);
+	\path[edge, ->] (v) -- (w) node[midway, below] {$e_1$};
+	\path[edge, ->] (v) -- (x) node[midway, below] {$e_2$};	
+	\path[edge] (0,1.5) -- (l) -- (u);
+	
+	\draw[left edge] (w) .. controls (-2, 5) .. (u);
+	\draw[right edge] (x) .. controls (2, 5) .. (u);
+	\draw[back edge] (x) .. controls (3, 5) .. (l) node[at end, right] {$lowpt(v_2)$};	
+	\end{tikzpicture} 
+	
+	\caption{Lowpoint}
+\end{wrapfigure}
+Hierfür wird der Begriff des \emph{Lowpoint} benötigt. Der Lowpoint $lowpt(v)$ eines Knotens ist derjenige Knoten, der mittels einer Rückwärtskante von ihm selbst oder eines seiner Kinder erreicht werden kann und der Wurzel am nächsten ist (dessen DFS-Index also am kleinsten ist). Existiert kein solcher Knoten oder nur solche, die von der Wurzel weiter entfernt sind als $v$, so ist der Lowpoint eines Knotens der Knoten selbst. Der Lowpoint einer Kante $e = (u, v)$ ist definiert als $lowpt(e) = \min\{lowpt(v), u\}$.
+
+\subsection{LR-Zerlegung}
+Es gibt zwei Klassen von Kreisen in einer Zeichnung eines planaren Graphen, diejenigen im und diejenigen gegen den Uhrzeigersinn. Teilen sich zwei Kreise einen Baumpfad so können sie sich potentiell überschneiden. Solche Überschneidungen können nur vermieden werden, indem ein Kreis komplett innerhalb des anderen gezeichnet wird. Abbildung \ref{lr:conf} führt intuitiv zur Aussage wann Kreise ineinander \emph{verschachtelt} sein können.
+
+\begin{figure} [h!tb]
+	\centering
+	\begin{tikzpicture}[auto]
+	\useasboundingbox (-2, 0.5) rectangle (7, 5);	
+	
+    \draw[edge] (0,0.5) -- (0,3);
+    \draw[edge] (-1.5,4) -- (0,3) node[midway, above] {};
+    \draw[edge] (1.5,4) -- (0,3) node[midway, above] {};
+    \node[vertex] at (0,3){$v$};
+    
+    \draw[left edge, rounded corners] (-1.5,4) .. controls (-0.5,1) .. (0,1);
+    \draw[right edge] (1.5,4) .. controls (0.5,2) .. (0,2);    
+
+    \draw[edge] (4.5,0.5) -- (4.5,3);
+    \draw[edge] (3,4) -- (4.5,3) node[midway, above] {};
+    \draw[edge] (6,4) -- (4.5,3) node[midway, above] {};
+    \node[vertex] at (4.5,3){$v$};
+    
+    \draw[right edge, rounded corners] (3,4) .. controls (8.5,6) and (5.5,1) .. (4.5,1);
+    \draw[right edge] (6,4) .. controls (5,2) .. (4.5,2);   
+	\end{tikzpicture}
+	\caption{Mögliche Konfigurationen für Kreise mit gemeinsamen Baumpfaden ohne symmetrische Fälle.}
+	\label{lr:conf}
+\end{figure}
+
+\begin{observation}
+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.
+
+\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.
+\end{observation}
+
+\begin{figure}[htb]
+	\centering
+\begin{tikzpicture}[auto, scale=0.65]
+	\useasboundingbox (-4,0) rectangle (4,6);
+
+    \foreach \pos/\name in {{(0,1)/a},{(0,2)/b},{(1,3)/c},{(0.75,4)/d},{(-0.5,4.5)/e},
+                            {(-1.5,3.5)/f}, {(1.25,5.25)/g},
+                            {(0,5.5)/h}, {(2.5,6)/i}, {(4,5)/j},{(2.5,4.5)/k},
+                            {(-2,6)/l}, {(-2.5,5)/m}, {(-4,5)/n}}
+        \node[small vertex] (\name) at \pos {};
+        
+    \foreach \source/ \dest in {a/b, b/c, c/d, d/e, e/f, e/g,
+                                e/h, h/i, i/j, j/k,
+                                h/l, l/m, m/n}
+        \path[tree edge] (\source) -- (\dest); 
+        
+    \foreach \source/ \dest in {f/b, m/e, n/a}
+        \path[left edge] (\source) -- (\dest);     
+        
+    \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}}
+	\label{lr:graph}	
+\end{figure}
+
+\begin{definition}[LR-Zerlegung]
+	Sei $G = (V, T \uplus B)$ ein DFS-orientierter Graph. Eine Zerlegung $B = L \uplus R$ seiner Rückwärtskanten heißt \emph{LR-Zerlegung} wenn für jeden Knoten mit ausgehenden Kanten $e_1$, $e_2$ gilt:
+	\begin{itemize}
+		\item Alle Rückwärtskanten von $e_1$ mit ihrem Ende über $lowpt(e_2)$ gehören zur einen und
+		\item Alle Rückwärtskanten von $e_2$ mit ihrem Ende über $lowpt(e_1)$ gehören zur anderen Klasse.
+	\end{itemize}
+	\label{lr:def}
+\end{definition}
+
+
+
+\subsection{LR-Ordnung}
+Es soll nun gezeigt werden, dass die Existenz einer LR-Zerlegung eine Charakterisierung der Planarität darstellt.
+
+\begin{theorem}
+\label{lr:thm}
+Ein Graph ist genau dann planar wenn er eine LR-Zerlegung zulässt.
+\end{theorem}
+
+Die Notwendigkeit der Bedingung ist klar, da aus einer gegebenen planaren Zeichnung und einer DFS-Orientierung sofort eine LR-Zerlegung erzeugt werden kann, indem die Kanten in ihre jeweiligen Gruppen eingeteilt werden. Um zu zeigen, dass die Bedingung hinreichend ist, wird im Folgenden aus einer LR-Zerlegung eine planare Einbettung erzeugt.
+
+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.
+
+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.
+
+\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:
+\begin{figure}[h!]
+\begin{minipage}[b]{0.25\linewidth}
+\centering
+	\begin{tikzpicture}[scale=0.3]
+	\useasboundingbox (-5, 0.5) rectangle (5, 6);	
+	
+	\node[vertex] (u) at (0,0.5) {$u$};
+	\node[vertex] (v) at (0,3) {$v$};
+	\node[very small vertex] (w) at (-3.5,3) {};
+	\node[very small vertex] (x) at (-1.5,6) {};	
+	\node[very small vertex] (b) at (1.5,6) {};	
+	\node[very small vertex] (c) at (3.5,3) {};			
+	
+	\path[edge, ->] (u) -- (v);
+	\path[left edge] (v) -- (w) node[near end, below, black] {$e_l^L$};
+	\path[left edge] (v) -- (x) node[very near end, below left, black] {$e_1^L$};
+	\path[right edge] (v) -- (b) node[very near end, below right, black] {$e_1^R$};
+	\path[right edge] (v) -- (c) node[near end, below, black] {$e_r^R$};
+	
+	\end{tikzpicture}
+\end{minipage}
+\begin{minipage}[b]{0.45\linewidth}
+\centering	
+\begin{align*}
+	&(u, v),\\
+	&L(e_l^L),e_l^L,R(e_l^L),\ldots,R(e_1^L),\\
+	&L(e_1^R),\ldots,L(e_r^R),e_r^R,R(e_r^R)
+\end{align*}
+\end{minipage}
+\begin{minipage}[b]{0.25\linewidth}
+\centering
+	\begin{tikzpicture}[auto, scale=0.3]
+	\useasboundingbox (-5, 0.5) rectangle (5, 6);	
+	
+	\node[vertex] (u) at (0,0.5) {$u$};
+	\node[vertex] (v) at (0,3) {$v$};
+	\node[very small vertex] (w) at (-3,6) {};
+	\node[very small vertex] (x) at (3,6) {};	
+	
+	\path[edge, ->] (u) -- (v);
+	\path[left edge] (v) -- (w) node[near end, below, black] {$e^L$};
+	\path[right edge] (v) -- (x) node[near end, below, black] {$e^R$};
+	
+	\draw[edge] (w) -- (-4,7);
+	\draw[left edge] (-4,7) .. controls(-4, 3.5) .. (v);
+	\draw[left edge] (-4,7) .. controls(-3, 3.5) .. (v);	
+	\draw[right edge] (-4,7) .. controls(-2, 7) .. (v);	
+	
+	\draw[edge] (x) -- (4,7);
+	\draw[right edge] (4,7) .. controls(4, 3.5) .. (v);	
+	\draw[left edge] (4,7) .. controls(2, 7) .. (v);	
+	\end{tikzpicture}
+\end{minipage}
+\end{figure}
+
+
+$L(e)$ und $R(e)$ bezeichnen die linken und rechten eingehenden Kanten der Kreise die sich $e$ teilen. Die Verschachtelung dieser Kanten verhält sich wie die Verschachtelung der Kanten an der entsprechenden Gabelung.
+\end{definition}
+
+\begin{lemma}
+Eine \emph{LR-Ordnung} stellt eine planare Einbettung einer \emph{LR-Zerlegung} dar.
+\end{lemma}
+Ein Beweis durch Widerspruch findet sich in \cite{Bra09}. Die Existenz einer \emph{LR-Zerlegung} ist also ein Planaritätskriterium.
 
 \section{Anwendung des Kriteriums}
-\subsection{Kantenverschachtelung}
-Salat.
-\subsection{Polynomialzeitalgorithmus}
+Das LR-Planaritätskriterium zeigt, dass das Testen auf Planarität einem Testen auf die Existenz einer LR-Zerlegung entspricht. Hier soll nun mit Hilfe des Kriteriums ein polynomieller Algorithmus konstruiert werden, \cite{Bra09} beschreibt, wie durch weniger explizites Arbeiten ein Linearzeitalgorithmus auf Basis des Kriteriums implementiert werden kann.
+
+Sei $G = (V, T \uplus B)$ eine DFS-Orientierung von G. Es muss also überprüft werden, ob $B$ eine LR-Zerlegung zulässt. Dafür müssen für alle Gabelungen alle Bedingungen gleichzeitig erfüllt werden können. Aus Definition \ref{lr:def} ergeben sich direkt die folgenden Bedingungen für Kanten.
+
+\begin{lemma}
+	Seien $b_1 = (u_1, v_1)$ und $b_2 = (u_2, v_2)$ \emph{zwei Rückwärtskanten} mit überlappenden Zyklen und sei $(u, v)$, $(v, w_1)$, $(v, w_2)$ ihre Gabelung. Außerdem sei $C(b)$ die Menge der Knoten, die sich auf dem durch b definierten Zyklus befinden. Dann gilt:
+	\begin{enumerate}
+		\item $b_1$ und $b_2$ gehören zu \emph{verschiedenen} Klassen wenn $lowpt(w_2) < v_1$ und $lowpt(w_1) < v_2$
+		\item $b_1$ und $b_2$ gehören zur \emph{selben} Klasse wenn es eine Kante $e' = (x, y)$ gibt, sodass $x \in C(b_1) \cap C(b_2)$ und $y \not\in C(b_1) \cap C(b_2)$ und  $lowpt(y) < min\{v_1, v_2\}$
+	\end{enumerate}
+\end{lemma}
 
-\subsection{Linearzeitalgorithmus}
+\begin{figure}
+	\hspace*{\fill}
+	\subfloat[]{
+	\begin{tikzpicture}[auto, scale=0.5]
+	\useasboundingbox (-4, 0) rectangle (4, 9);	
+	
+	\node[small vertex] (u) at (0,3) {};
+	\node[small vertex] (v) at (0,6) {$v$};
+	\node[small vertex] (w) at (-2,8) {$w_1$};	
+	
+	\path[edge] (u) -- (v);
+	\path[edge, ->] (v) -- (w);
+	\draw[edge] (0,0) -- (u);
+	\draw[edge] (v) -- (2, 8);
+	
+	\draw[left edge] (w) .. controls (-2, 5) .. (u);
+	\draw[back edge] (w) .. controls (-3, 5) .. (0,1);
+	
+	\draw[right edge] (2, 8) .. controls (2, 4) .. (0,2);
+	\end{tikzpicture}
+	}
+	\hspace*{\fill}
+	\subfloat[]{	
+	\begin{tikzpicture}[auto, scale=0.5]
+	\useasboundingbox (-4, 0) rectangle (4, 9);	
+	
+	\node[small vertex] (u) at (0,3) {};
+	\node[small vertex] (v) at (0,6) {$v$};
+	\node[small vertex] (w) at (-2,8) {$w_1$};	
+	\node[small vertex] (x) at (2,8) {$w_2$};
+	
+	\path[edge] (u) -- (v);
+	\path[edge, ->] (v) -- (w);
+	\path[edge, ->] (v) -- (x);	
+	\draw[edge] (0,0) -- (u);
+	
+	\draw[left edge] (w) .. controls (-2, 5) .. (u);
+	\draw[right edge] (x) .. controls (2, 5) .. (u);
+	\draw[back edge] (w) .. controls (-3, 5) .. (-1,1);
+	\draw[back edge] (x) .. controls (3, 5) .. (1,1);	
+	\end{tikzpicture}
+	}
+	\hspace*{\fill}
+	\subfloat[]{	
+	\begin{tikzpicture}[auto, scale=0.5]
+	\useasboundingbox (-4, 0) rectangle (4, 9);	
+	
+	\node[small vertex] (u) at (0,3) {$v_2$};
+	\node[small vertex] (v) at (0,5) {$v_1$};
+	\node[small vertex] (w) at (0,7) {$x$};	
+	\node[small vertex] (x) at (0,9) {};
+	
+	\path[edge] (u) -- (v);
+	\path[edge] (v) -- (w);
+	\path[edge] (w) -- (x);	
+	\draw[edge] (0,0) -- (u);
+	
+	\draw[right edge] (x) .. controls (3, 7) .. (u);
+	\draw[right edge] (x) .. controls (1.5, 7) .. (v);
+	\draw[back edge] (w) .. controls (-2, 5) .. (0,1);	
+	\end{tikzpicture}	
+	}
+	\hspace*{\fill}
+	\caption{Die Bedingungen für Rückwärtskanten ergeben sich dur drei Arten von Minimalkonfigurationen (\cite{Bra09}). (a) und (b) zeigen Verschieden-Bedingungen, (c) zeigt eine Gleich-Bedingung}
+\end{figure}
 
+Unterliegt ein Paar von Rückwärtskanten sowohl einer Verschieden- als auch einer Gleich-Bedingung, kann keine LR-Partition existieren und der Graph ist nicht planar. Weitergehend können die Bedingungen in einem \emph{Constraint-Graph} dargestellt werden, wobei Kanten mit Verschieden-Bedingungen eine andere Markierung bekommen als solche mit einer Gleich-Bedingung. Werden nun alle Kanten mit Gleich-Bedingungen kontrahiert muss der Graph auf Bipartitheit überprüft werden, um zu entscheiden, ob eine LR-Zerlegung existiert und damit, ob der Graph planar ist. Dieser Algorithmus hat quadratische Laufzeit (\cite{Bra09}).
 \bibliographystyle{alpha}
 \bibliography{term_paper}