--- a/planarity/beamerthemeLEA2.sty	Tue May 22 02:05:30 2012 +0200
+++ b/planarity/beamerthemeLEA2.sty	Wed May 23 12:46:05 2012 +0200
@@ -56,4 +56,5 @@
 
 \setbeamercovered{transparent}
 
-\lstset{escapeinside=`´, numbers=left, numberstyle=\tiny, numbersep=5pt, basicstyle=\small, backgroundcolor=\color{tumlightblue}}
+% removed escapeinside=
+\lstset{numbers=left, numberstyle=\tiny, numbersep=5pt, basicstyle=\small, backgroundcolor=\color{tumlightblue}}

Binary file planarity/presentation.pdf has changed

--- a/planarity/presentation.tex	Tue May 22 02:05:30 2012 +0200
+++ b/planarity/presentation.tex	Wed May 23 12:46:05 2012 +0200
@@ -3,7 +3,7 @@
 
 \usepackage[ngerman,english]{babel}
 \usepackage[T1]{fontenc}
-\usepackage[latin1]{inputenc}
+\usepackage[utf8]{inputenc}
 \usepackage{amsmath}
 \usepackage{amsthm}
 \usepackage{amsfonts}
@@ -20,7 +20,7 @@
 
 %\bibliographystyle{plainnat}
 
-\newcommand{\N}       {\mathbb{N}}          % natürliche Zahlen
+\newcommand{\N}       {\mathbb{N}}          % natürliche Zahlen
 \newcommand{\Z}       {\mathbb{Z}}          % ganze Zahlen
 \newcommand{\R}       {\mathbb{R}}          % reelle Zahlen
 \newcommand{\Prob}    {\mathrm{P}}          % Wahrscheinlichkeit
@@ -56,12 +56,12 @@
 \tikzstyle{selected edge} = [draw,line width=5pt,-,red!50]
 
 
-\title{Testen eines Graphen auf Planarität}
+\title{Testen eines Graphen auf Planarität}
 \subtitle{Proseminar ``Graph Drawing''}
 \author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}} 
 %\date{\today}
 \date{2012-05-22}
-\institute{Technische Universität München}
+\institute{Technische Universität München}
 %Inhaltsverzeichnis zu Begin von jedem Abschnitt einblenden?
 %\AtBeginSection[]{
 %  \begin{frame}
@@ -95,9 +95,9 @@
 		\item<1-> $E \subseteq V^2$, $|V| = n$, $|E| = m$
 		\vspace{1em}
 		\item<2-> \alert{einfach}: Keine Schleifen oder Mehrfachkanten
-		\item<2-> \alert{zusammenhängend}: Es existiert ein Pfad von jedem Knoten zu jedem Knoten
-		\item<2-> \alert{Baum}: Zyklenfreier zusammenhängender Graph
-		\item<2-> \alert{$k$-zusammenhängend}: Zusammenhängend nach Entfernen von $k-1$ Knoten
+		\item<2-> \alert{zusammenhängend}: Es existiert ein Pfad von jedem Knoten zu jedem Knoten
+		\item<2-> \alert{Baum}: Zyklenfreier zusammenhängender Graph
+		\item<2-> \alert{$k$-zusammenhängend}: Zusammenhängend nach Entfernen von $k-1$ Knoten
 	\end{itemize}
 \end{frame}
 
@@ -157,7 +157,7 @@
 \end{frame}
 
 \begin{frame}
-	\frametitle{Planarität}
+	\frametitle{Planarität}
 	\begin{itemize}
 		\item \alert{offene Jordankurve}	
 		\vspace{0.2em}
@@ -172,9 +172,9 @@
 		\vspace{1em}
 
 		\item<2-> Eine \alert{Zeichnung} ordnet in $\R^2$ jedem Knoten Koordinaten und jeder Kante eine offene Jordankurve zu
-		\item<2-> \alert{äquivalent}: Gleiche Reihenfolge der Kanten an Knoten
+		\item<2-> \alert{äquivalent}: Gleiche Reihenfolge der Kanten an Knoten
 		\vspace{2em}
-		\item<2-> \alert{planar}: Keine sich überschneidenden Kurven
+		\item<2-> \alert{planar}: Keine sich überschneidenden Kurven
 	\end{itemize}
 \end{frame}
 
@@ -184,8 +184,8 @@
 	\begin{theorem}
 	Ein Graph ist genau dann planar wenn\ldots
 	\begin{itemize}
-		\item \alert{Kuratowski} (1930): er keinen Teilgraphen enthält der eine Unterteilung von $K_5$ oder $K_{3,3}$ ist.
-		\item \alert{Wagner} (1937): er nicht $K_5$ oder $K_{3,3}$ als Minoren enthält.
+		\item \alert{Kuratowski} (1930): er keinen Teilgraphen enthält der eine Unterteilung von $K_5$ oder $K_{3,3}$ ist.
+		\item \alert{Wagner} (1937): er nicht $K_5$ oder $K_{3,3}$ als Minoren enthält.
 	\end{itemize}
 	\end{theorem}
 
@@ -211,14 +211,14 @@
 \end{frame}
 
 \begin{frame}
-	\frametitle{Vorüberlegungen}
+	\frametitle{Vorüberlegungen}
 	\begin{columns}[T]
 		\begin{column}{.6\textwidth}
 			\begin{itemize}
 				\item<1,5> \alert{Schleifen} entfernen
 				\item<1,5> \alert{Parallele Kanten} entfernen
 				\item<2,5> \alert{Zusammenhangskomponenten} getrennt betrachten
-				\item<3,5> \alert{Blöcke} getrennt betrachten
+				\item<3,5> \alert{Blöcke} getrennt betrachten
 				\item<3,5> Knoten von \alert{Grad 1} entfernen
 				\item<4,5> Knoten von \alert{Grad 2} durch Kanten ersetzen
 			\end{itemize}
@@ -293,9 +293,9 @@
 		\vspace{2em}
 		\item \alert{Kreisbasiert}
 		\begin{itemize}
-			\item Nur Graphen mit Zyklen können nicht planar sein
+			\item Nur Graphen mit Zyklen können nicht planar sein
 			\item Zyklen trennen Ebene in zwei Bereiche
-			\item Teilgraphen sind entweder innen oder außen
+			\item Teilgraphen sind entweder innen oder außen
 		\end{itemize}
 	\end{itemize}
 \end{frame}
@@ -322,11 +322,11 @@
 			\begin{itemize}
 				\item Wurzel
 				\item DFS-Baum
-				\item Rückwärtskante
+				\item Rückwärtskante
 				\item Orientierung
 				\vspace{2em}
 				\item<2> DFS-Index
-				\item<2> strikt höher/tiefer
+				\item<2> strikt höher/tiefer
 				\item<2> \alert{lowpoint}\\ $lowpt([5]) = 2$
 			\end{itemize}
 		\end{column}
@@ -408,9 +408,9 @@
 	\frametitle{LR-Zerlegung}
 	
 	\begin{itemize}
-		\item Jede Rückwärtskante erzeugt einen \alert{Zyklus}
+		\item Jede Rückwärtskante erzeugt einen \alert{Zyklus}
 		\item LR-Zerlegung teilt Zyklen in solche im und gegen den Uhrzeigersinn
-		\item Quelle \alert{außen}
+		\item Quelle \alert{außen}
 		\item \alert{Verschachtelung} nur bei gleicher Orientierung
 	\end{itemize}
 	
@@ -442,10 +442,10 @@
 	\frametitle{LR-Zerlegung}
 	
 	\begin{definition}
-		Sei $G = (V, T \uplus B)$ ein \alert{DFS-orientierter} Graph. Eine Zerlegung $B = L \uplus R$ seiner Rückwärtskanten heißt \alert{LR-Zerlegung} wenn für jeden Knoten mit ausgehenden Kanten $e_1$, $e_2$ gilt:
+		Sei $G = (V, T \uplus B)$ ein \alert{DFS-orientierter} Graph. Eine Zerlegung $B = L \uplus R$ seiner Rückwärtskanten heißt \alert{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.
+			\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}
 	\end{definition}
 	
@@ -477,7 +477,7 @@
 	\frametitle{LR-Zerlegung}
 
 	\begin{theorem}
-		Ein Graph ist genau dann planar, wenn er eine \alert{LR-Zerlegung} zulässt.
+		Ein Graph ist genau dann planar, wenn er eine \alert{LR-Zerlegung} zulässt.
 	\end{theorem}
 		
 	\vspace{2em}	
@@ -486,9 +486,9 @@
 		\item Planare Zeichnung $\rightarrow$ LR-Zerlegung intuitiv
 		\vspace{1em}
 		\item Andere Richtung: Konstruktiv
-		\item Probleme ergeben sich bei überlappenden Kreisen
-		\item Welche Kreise liegen außen, welche innen?
-		\item Bedingungen abhängig von Baumkanten
+		\item Probleme ergeben sich bei überlappenden Kreisen
+		\item Welche Kreise liegen außen, welche innen?
+		\item Bedingungen abhängig von Baumkanten
 	\end{itemize}
 \end{frame}
 
@@ -496,7 +496,7 @@
 	\frametitle{Verschachtelung}
 	
 	\begin{block}{Beobachtung}
-	Die Baumkante $e_1$ muss außerhalb von Baumkante sein $e_2$ wenn
+	Die Baumkante $e_1$ muss außerhalb von Baumkante sein $e_2$ wenn
 	\begin{itemize}
 		\item $lowpt(e_1) < lowpt(e_2)$
 	\end{itemize}
@@ -540,10 +540,10 @@
 			&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*}
-		Dabei ist \alert{$e_1$} außerhalb von \alert{$e_2$} usw.
+		Dabei ist \alert{$e_1$} außerhalb von \alert{$e_2$} usw.
 	\end{definition}
 
-	\alert{$L(e)$} bezeichnet die linken eingehenden Rückwärtskanten deren Kreise sich $e$ teilen.
+	\alert{$L(e)$} bezeichnet die linken eingehenden Rückwärtskanten deren Kreise sich $e$ teilen.
 \end{frame}
 
 \begin{frame}
@@ -614,7 +614,7 @@
 		Beweis durch Widerspruch
 		\begin{itemize}
 			\item \alert{Baumkanten} sind immer planar
-			\item Überschneidungen wenn dann nur in \alert{Rückwärtskanten}
+			\item Überschneidungen wenn dann nur in \alert{Rückwärtskanten}
 			\item Fallunterscheidung
 			\begin{itemize}
 				\item selbe Klasse
@@ -628,15 +628,15 @@
 	\frametitle{Algorithmus}
 	
 	\begin{itemize}
-		\item Testen auf Planarität entspricht Testen auf \alert{LR-Zerlegung}	
+		\item Testen auf Planarität entspricht Testen auf \alert{LR-Zerlegung}	
 		\item \alert{LR-Zerlegung} stellt Randbedingungen
 		\vspace{2em}
 		\item Welche Bedingungen gibt es?
 		\begin{itemize}
-			\item Überlappende Kreise
+			\item Ãœberlappende Kreise
 			\item Gabelungen
 		\end{itemize}
-		\item Können alle Bedingungen gleichzeitig erfüllt werden?
+		\item Können alle Bedingungen gleichzeitig erfüllt werden?
 	\end{itemize}
 \end{frame}
 
@@ -714,10 +714,10 @@
 \begin{frame}
 	\frametitle{Algorithmus}
 	\begin{block}{Korollar}
-		Seien $b_1 = (u_1, v_1)$ und $b_2 = (u_2, v_2)$ \alert{zwei Rückwärtskanten} mit überlappenden Zyklen und sei $(u, v)$, $(v, w_1)$, $(v, w_2)$ ihre Gabelung. Dann gilt:
+		Seien $b_1 = (u_1, v_1)$ und $b_2 = (u_2, v_2)$ \alert{zwei Rückwärtskanten} mit überlappenden Zyklen und sei $(u, v)$, $(v, w_1)$, $(v, w_2)$ ihre Gabelung. Dann gilt:
 		\begin{itemize}
-			\item $b_1$ und $b_2$ gehören zu \alert{verschiedenen} Klassen wenn $lowpt(w_2) < v_1$ und $lowpt(w_1) < v_2$
-			\item $b_1$ und $b_2$ gehören zur \alert{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\}$
+			\item $b_1$ und $b_2$ gehören zu \alert{verschiedenen} Klassen wenn $lowpt(w_2) < v_1$ und $lowpt(w_1) < v_2$
+			\item $b_1$ und $b_2$ gehören zur \alert{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{itemize}
 	\end{block}
 	
@@ -729,8 +729,8 @@
 
 	\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
+		\item Rückwärtskanten werden Knoten
+		\item Abhängigkeiten werden Kanten mit Beschriftung
 	\end{itemize}
 \end{frame}
 
@@ -817,7 +817,7 @@
 \begin{frame}
 	\frametitle{Q \& A}
 
-	\begin{center} \LARGE Danke für die Aufmerksamkeit!\end{center} 	
+	\begin{center} \LARGE Danke für die Aufmerksamkeit!\end{center} 	
 	\vspace{1em}	
 	\begin{center} \LARGE Fragen?\end{center} 	
 \end{frame}
@@ -866,9 +866,9 @@
 				\item Kreise enthalten \alert{Segmente}
 				\begin{itemize}
 					\item Kanteninduzierte Teilgraphen
-					\item Mindestens zwei Aufhängungnen (\emph{attachments})
+					\item Mindestens zwei Aufhängungnen (\emph{attachments})
 				\end{itemize}
-				\item \alert{Kompatible} Segmente können auf der selben Facette gezeichnet werden.
+				\item \alert{Kompatible} Segmente können auf der selben Facette gezeichnet werden.
 				\vspace{1.5em}
 				\item<2> Sehne (\emph{chord})
 				\item<3> Teilgraph als Segment
@@ -909,18 +909,18 @@
 \end{frame}
 
 \begin{frame}
-	\frametitle{Kompatibilität}
+	\frametitle{Kompatibilität}
 	\begin{Lemma}
-		Zwei Segmente sind genau dann \alert{kompatibel}, wenn ihre Aufhängungen nicht verflochten (\emph{interleaved}) sind.
+		Zwei Segmente sind genau dann \alert{kompatibel}, wenn ihre Aufhängungen nicht verflochten (\emph{interleaved}) sind.
 	\end{Lemma}
 	
 	\vspace{2em}
 	
 	\begin{theorem}<2>
-		Ein \alert{2-zusammenhängender} Graph mit Kreis $C$ ist planar genau dann wenn
+		Ein \alert{2-zusammenhängender} Graph mit Kreis $C$ ist planar genau dann wenn
 		\begin{itemize}
 			\item Der \alert{Verflechtungsgraph} der Segmente von C \alert{bipartit} ist
-			\item Für alle Segmente $P$ der Graph \alert{$P \cup C$ planar} ist
+			\item Für alle Segmente $P$ der Graph \alert{$P \cup C$ planar} ist
 		\end{itemize}
 	\end{theorem}
 \end{frame}
@@ -928,10 +928,10 @@
 \begin{frame}
 	\frametitle{Auslander-Parter}
 	\begin{block}{Algorithmus}
-		Rekursives Betrachten der Kreise und Teilgraphen mit drei Fällen:
+		Rekursives Betrachten der Kreise und Teilgraphen mit drei Fällen:
 		\begin{itemize}
 			\item \textbf{Trivialer Fall} Der Graph $G$ ist ein einfacher Kreis $C$. Tritt nur am Anfang auf.
-			\item \textbf{Basisfall} Der Kreis $C$ enthält ein einziges Segment, das ein Pfad ist.
+			\item \textbf{Basisfall} Der Kreis $C$ enthält ein einziges Segment, das ein Pfad ist.
 			\item \textbf{Rekursionsfall} Ein Kreis mit mehreren Segmenten oder Subgraphen ist in $G$ enthalten. Anwendung des Theorems und rekursive Abarbeitung der Subgraphen.
 		\end{itemize}
 	\end{block}
@@ -939,7 +939,7 @@
 	\vspace{0.5em}
 	\begin{itemize}
 		\item $\Oh(n)$ Rekursionen mit Verflechtungsgraphen in $\Oh(n^2)$\\
-		\item Gesamtkomplexität $\Oh(n^3)$
+		\item Gesamtkomplexität $\Oh(n^3)$
 	\end{itemize}
 \end{frame}
 \end{document}