--- a/planarity/presentation.tex	Tue May 08 23:17:51 2012 +0200
+++ b/planarity/presentation.tex	Wed May 09 00:25:18 2012 +0200
@@ -232,7 +232,7 @@
 	\begin{itemize}
 		\item Wie sieht eine Planare Zeichnung (\emph{embedding}) aus?
 		\item Ausstellen von Zertifikaten zur Nichtplanarität
-		\item Was ist der maximale planare Teilgraph? (NP hart)
+		\item Was ist der maximale planare Teilgraph? (NP vollständig)
 	\end{itemize}
 \end{frame}
 
@@ -424,10 +424,10 @@
 	\end{block}
 	
 	\vspace{0.5em}
-	\begin{center}
-		$\Oh(n)$ Rekursionen mit Verflechtungsgraphen der Größe $\Oh(n^2)$\\
-		$\Rightarrow \Oh(n^3)$
-	\end{center}
+	\begin{itemize}
+		\item $\Oh(n)$ Rekursionen mit Verflechtungsgraphen der Größe $\Oh(n^2)$\\
+		\item Gesamtkomplexität $\Oh(n^3)$
+	\end{itemize}
 \end{frame}
 
 \subsubsection{de Fraysseix-Ossona de Mendez-Rosenstiehl}
@@ -662,18 +662,171 @@
 	\end{block}
 \end{frame}
 
+\begin{frame}
+	\frametitle{Algorithmus}
+	
+	\begin{columns}[T]
+		\begin{column}{.6\textwidth}
+			\begin{columns}[T]
+				\begin{column}{.5\textwidth}
+	\begin{figure}
+	\begin{tikzpicture}[auto, scale=0.5]
+	\useasboundingbox (-5, 0) rectangle (5, 6);	
+	
+	\node[vertex] (u) at (0,0) {$u$};
+	\node[vertex] (v) at (0,3) {$v$};
+	\node[vertex] (w) at (-4,3) {$e_l^L$};
+	\node[vertex] (x) at (-3,5) {$e_2^L$};
+	\node[vertex] (y) at (-1,6) {$e_1^L$};		
+	\node[vertex] (a) at (1,6) {$e_1^R$};	
+	\node[vertex] (b) at (3,5) {$e_2^R$};	
+	\node[vertex] (c) at (4,3) {$e_r^R$};			
+	
+	\path[edge, ->] (u) -- (v);
+	\path[left edge] (v) -- (w);
+	\path[left edge] (v) -- (x);
+	\path[left edge] (v) -- (y);
+	\path[right edge] (v) -- (a);
+	\path[right edge] (v) -- (b);
+	\path[right edge] (v) -- (c);
+	
+	\end{tikzpicture}
+	\end{figure}				
+				\end{column}
+				\begin{column}{.5\textwidth}
+	\begin{figure}
+	\begin{tikzpicture}[auto, scale=0.5]
+	\useasboundingbox (-5, 0) rectangle (5, 6);	
+	
+	\node[vertex] (u) at (0,0) {$u$};
+	\node[vertex] (v) at (0,3) {$v$};
+	\node[vertex] (w) at (-4,3) {$e_l^L$};
+	\node[vertex] (x) at (-3,5) {$e_2^L$};
+	\node[vertex] (y) at (-1,6) {$e_1^L$};		
+	\node[vertex] (a) at (1,6) {$e_1^R$};	
+	\node[vertex] (b) at (3,5) {$e_2^R$};	
+	\node[vertex] (c) at (4,3) {$e_r^R$};			
+	
+	\path[edge, ->] (u) -- (v);
+	\path[left edge] (v) -- (w);
+	\path[left edge] (v) -- (x);
+	\path[left edge] (v) -- (y);
+	\path[right edge] (v) -- (a);
+	\path[right edge] (v) -- (b);
+	\path[right edge] (v) -- (c);
+	
+	\end{tikzpicture}
+	\end{figure}				
+				\end{column}
+			\end{columns}
+		\end{column}
+		\begin{column}{.4\textwidth}
+	\begin{figure}
+	\begin{tikzpicture}[auto, scale=0.5]
+	\useasboundingbox (-5, 0) rectangle (5, 6);	
+	
+	\node[vertex] (u) at (0,0) {$u$};
+	\node[vertex] (v) at (0,3) {$v$};
+	\node[vertex] (w) at (-2,5) {$e^L$};
+	\node[vertex] (x) at (2, 5) {$e^R$};	
+	
+	\path[edge, ->] (u) -- (v);
+	\path[left edge] (v) -- (w);
+	\path[right edge] (v) -- (x);
+	
+	\draw[edge] (w) -- (-4,7);
+	\draw[left edge] (-4,7) .. controls(-4, 3.5) .. (v);
+	\draw[left edge] (-4,7) .. controls(-2.5, 3.5) .. (v);	
+	\draw[right edge] (-4,7) .. controls(-2, 7) .. (v);	
+	
+	\draw[edge] (x) -- (4,7);
+	\draw[left edge] (4,7) .. controls(4, 3.5) .. (v);	
+	\draw[right edge] (4,7) .. controls(2, 7) .. (v);	
+	\end{tikzpicture}
+	\end{figure}	
+		\end{column}
+	\end{columns}
+\end{frame}
+
+\begin{frame}
+	\frametitle{Algorithmus}
+
+	\begin{itemize}
+		\item Die Bedingungen lassen sich in einem \alert{Constraint Graphen} darstellen
+		\item Rückwärtskanten werden Knoten
+		\item Abhängigkeiten werden Kanten mit Beschriftung
+	\end{itemize}
+	
+	\begin{center}
+		Ich bin ein Constraintgraph
+	\end{center}
+\end{frame}
+
+\begin{frame}
+	\frametitle{FMR}
+	
+	\begin{block}{Algorithmus}
+		Rekursives Betrachten der Kreise und Teilgraphen mit drei Fällen:
+		\begin{itemize}
+			\item Erstellen einer \alert{DFS-Orientierung}
+			\item Berechnen von \alert{lowpoints}
+			\item Erzeugen des \alert{Constraint Graphs}
+			\item Ist dieser Widerspruchsfrei ist der Graph planar
+		\end{itemize}
+	\end{block}
+	
+	\vspace{0.5em}
+	\begin{itemize}
+		\item Erzeugen des Constraint Graphen hat eine Komplexität von $\Oh(n^2)$\\
+		\item Kann in $\Oh(n)$ implementiert werden, indem der Graph nicht explizit erzeugt wird.
+	\end{itemize}
+\end{frame}
+
 \subsection{Knotenbasiert}
 \begin{frame}[plain]
-	\begin{center} \LARGE Knotenbasierte Algorithmen \end{center} 	
+	\begin{center} \LARGE Knotenbasierte Algorithmen\end{center} 	
 \end{frame}
 
 \begin{frame}
 	\frametitle{Idee}
-	
+	\begin{itemize}
+		\item Ein Graph bleibt planar wenn man einzelne Knoten \alert{entfernt}
+		\vspace{1.5em}
+		\item Prozess kann \alert{umgekehrt} werden
+		\item Graph knotenweise vergrößern
+		\item Noch hinzuzufügender Graph muss zusammenhängend sein
+	\end{itemize}
 \end{frame}
 
 \begin{frame}
-	\frametitle{Boyer Myrvold}
+	\frametitle{Praktische Eigenschaften}
+	\begin{itemize}
+		\item Es existiert immer eine \alert{Kette} von Planaren Graphen
+		\item Einmal \alert{geschlossene Facetten} bleiben geschlossen
+		\item Die \alert{Reihenfolge} von Knoten um eine Facette bleibt erhalten
+	\end{itemize}
+	
+	\begin{figure}
+	\begin{tikzpicture}[auto]	
+    \foreach \pos/\name in {{(0,0)/a}, {(-3, 1)/b}, {(3, 1)/c},{(-2, 3)/d},
+                            {(2,2.5)/e}}
+        \node[small vertex] (\name) at \pos {};
+        
+    \foreach \source/ \dest in {a/b, a/c, c/e, b/d,
+                                a/d, e/a}
+        \path[edge] (\source) -- (\dest);	
+
+    \draw[dashed] (d) -- (-2, 4);
+    \draw[dashed] (d) -- (-1, 2.5);
+    \draw[dashed] (e) -- (2.5, 3);
+    \draw[dashed] (e) -- (1.5, 3.5);  
+	
+	\begin{pgfonlayer}{background}
+    \fill[red!50] (a.center) -- (b.center) -- (d.center);	
+    \fill[red!50] (a.center) -- (c.center) -- (e.center);	
+    \end{pgfonlayer}
+	\end{tikzpicture}
+	\end{figure}		
 \end{frame}
 
 \section{Q\&A}