Mercurial > latex

changeset 24:9ed5990afd4d

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add auslander parter as backup, fix some visualization errors, add proof idea
author Markus Kaiser <markus.kaiser@in.tum.de>
date Mon, 21 May 2012 16:52:04 +0200
parents e79e0b46fcdf
children 89b01b2ea447
files planarity/presentation.tex
diffstat 1 files changed, 157 insertions(+), 27 deletions(-) [+]
line wrap: on
line diff
--- a/planarity/presentation.tex	Mon May 21 15:12:26 2012 +0200
+++ b/planarity/presentation.tex	Mon May 21 16:52:04 2012 +0200
@@ -301,6 +301,19 @@
 \end{frame}
 
 \begin{frame}
+	\frametitle{LR-Algorithmus}
+	
+	\begin{itemize}
+		\item \alert{Kantenweises} betrachten des Graphen
+		\item Weiterentwicklung von \emph{Hopcroft und Tarjan} (1974)
+		\vspace{2em}
+		\item Original von \emph{de Fraysseix, Ossona de Mendez und
+Rosenstiehl} (2006)
+		\item Beschrieben von \emph{Ulrik Brandes} (2009)
+	\end{itemize}
+\end{frame}
+
+\begin{frame}
 	\frametitle{Tiefensuche}
 
 	\begin{columns}[T]
@@ -309,8 +322,10 @@
 				\item Wurzel
 				\item DFS-Baum
 				\item Rückwärtskante
+				\item Orientierung
 				\vspace{2em}
 				\item<2> DFS-Index
+				\item<2> strikt höher/tiefer
 				\item<2> \alert{lowpoint}\\ $lowpt([5]) = 2$
 			\end{itemize}
 		\end{column}
@@ -394,12 +409,32 @@
 	\begin{itemize}
 		\item Jede Rückwärtskante erzeugt einen \alert{Zyklus}
 		\item LR-Partition teilt Zyklen in solche im und gegen den Uhrzeigersinn
-		\item Gleiche Orientierung bei \alert{Verschachtelung}
-		
-		\vspace{2em}		
-		
-		\item In jedem planaren Graphen lassen sich Kreise so anordnen
+		\item Quelle \alert{außen}
+		\item \alert{Verschachtelung} nur bei gleicher Orientierung
 	\end{itemize}
+	
+	\begin{center}
+	\begin{figure}
+	\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] {};
+    
+    \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] {};
+    
+    \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}
+	\end{figure}
+	\end{center}	
 \end{frame}
 
 \begin{frame}
@@ -514,24 +549,24 @@
 		\begin{column}{.5\textwidth}
 	\begin{figure}
 	\begin{tikzpicture}[auto, scale=0.5]
-	\useasboundingbox (-5, 0) rectangle (5, 6);	
+	\useasboundingbox (-5, 0) rectangle (5, 8);	
 	
 	\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$};			
+	\node[small vertex] (w) at (-4,3) {};
+	\node[small vertex] (x) at (-3,6) {};
+	\node[small vertex] (y) at (-1,8) {};		
+	\node[small vertex] (a) at (1,8) {};	
+	\node[small vertex] (b) at (3,6) {};	
+	\node[small vertex] (c) at (4,3) {};			
 	
 	\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);
+	\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_2^L$};
+	\path[left edge] (v) -- (y) node[at end, below left, black] {$e_1^L$};
+	\path[right edge] (v) -- (a) node[at end, below right, black] {$e_1^R$};
+	\path[right edge] (v) -- (b) node[very near end, below right, black] {$e_2^R$};
+	\path[right edge] (v) -- (c) node[near end, below, black] {$e_r^R$};
 	
 	\end{tikzpicture}
 	\end{figure}
@@ -539,20 +574,20 @@
 		\begin{column}{.5\textwidth}
 	\begin{figure}
 	\begin{tikzpicture}[auto, scale=0.5]
-	\useasboundingbox (-5, 0) rectangle (5, 6);	
+	\useasboundingbox (-5, 0) rectangle (5, 8);	
 	
 	\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$};	
+	\node[small vertex] (w) at (-3,6) {};
+	\node[small vertex] (x) at (3,6) {};	
 	
 	\path[edge, ->] (u) -- (v);
-	\path[left edge] (v) -- (w);
-	\path[right edge] (v) -- (x);
+	\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(-2.5, 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);
@@ -572,9 +607,18 @@
 	\end{block}
 	\vspace{2em}
 	
-	\begin{itemize}
-		\item Beweis durch Widerspruch. <DO WORK HERE>
-	\end{itemize}
+	\begin{block}{Beweisidee}
+		Beweis durch \emph{Widerspruch}
+		\begin{itemize}
+			\item \alert{Baumkanten} sind immer planar
+			\item Überschneidungen wenn dann nur in \alert{Rückwärtskanten}
+			\item Fallunterscheidung
+			\begin{itemize}
+				\item selbe Klasse
+				\item verschiedene Klassen
+			\end{itemize}
+		\end{itemize}
+	\end{block}
 \end{frame}
 
 \begin{frame}
@@ -800,4 +844,90 @@
 	\end{tikzpicture}
 	\end{figure}		
 \end{frame}
+
+\begin{frame}
+	\frametitle{Segmente}
+	\begin{columns}[T]
+		\begin{column}{.6\textwidth}
+			\begin{itemize}
+				\item Jede Kante eines Blocks ist Teil von mindestens einem Kreis
+				\item Kreise enthalten \alert{Segmente}
+				\begin{itemize}
+					\item Kanteninduzierte Teilgraphen
+					\item Mindestens zwei Aufhängungnen (\emph{attachments})
+				\end{itemize}
+				\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
+			\end{itemize}
+		\end{column}
+		\begin{column}{.4\textwidth}	
+\begin{figure}
+\begin{tikzpicture}[auto, scale=0.8]
+    \foreach \pos/\name in {{(0,0)/a}, {(0,2)/b}, {(4,0)/c},{(4,2)/d},
+                            {(0,4)/e}, {(4,4)/f},
+                            {(0,6)/g}, {(0,8)/h},{(4,6)/i},{(4,8)/k},
+                            {(1.5,1)/l}, {(2.5,1)/m}, {(2,2)/n}}
+        \node[vertex] (\name) at \pos {};
+        
+    \foreach \source/ \dest in {a/b, a/c, c/d,
+                                b/e, d/f,
+                                e/g, g/h, h/k, k/i, i/f,
+                                g/k, h/f,
+                                l/m, m/n, n/l, a/l, m/d}
+        \path[edge] (\source) -- (\dest);        
+    
+    \foreach \vertex / \fr in {g/2, k/2, h/2, f/2,
+                               l/3, m/3, n/3, a/3, d/3
+                              }
+        \path<\fr> node[selected vertex] at (\vertex) {};
+        
+   \begin{pgfonlayer}{background}        
+   \foreach \source / \dest / \fr in {g/k/2, h/f/2,
+                                      l/m/3, m/n/3, n/l/3, a/l/3, m/d/3
+                                     }
+            \path<\fr>[selected edge] (\source) -- (\dest);
+   \end{pgfonlayer}  
+\end{tikzpicture}
+\end{figure}
+\vspace{1em}
+		\end{column}
+	\end{columns}	
+\end{frame}
+
+\begin{frame}
+	\frametitle{Kompatibilität}
+	\begin{Lemma}
+		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
+		\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
+		\end{itemize}
+	\end{theorem}
+\end{frame}
+
+\begin{frame}
+	\frametitle{Auslander-Parter}
+	\begin{block}{Algorithmus}
+		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{Rekursionsfall} Ein Kreis mit mehreren Segmenten oder Subgraphen ist in $G$ enthalten. Anwendung des Theorems und rekursive Abarbeitung der Subgraphen.
+		\end{itemize}
+	\end{block}
+	
+	\vspace{0.5em}
+	\begin{itemize}
+		\item $\Oh(n)$ Rekursionen mit Verflechtungsgraphen in $\Oh(n^2)$\\
+		\item Gesamtkomplexität $\Oh(n^3)$
+	\end{itemize}
+\end{frame}
 \end{document}