\documentclass[compress]{beamer}
%,hyperref={pdfpagelabels=false}

\usepackage[ngerman,english]{babel}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{helvet}
\usepackage{url}
\usepackage{listings}
\usepackage{xcolor}
\usepackage{xspace} % Abstand hinter Variablennamen
\usepackage{fix-cm}
\usepackage{tikz}
%\usepackage[square, sort, numbers, authoryear]{natbib}

\usepackage{beamerthemeLEA2}

%\bibliographystyle{plainnat}

\newcommand{\N}       {\mathbb{N}}          % natürliche Zahlen
\newcommand{\Z}       {\mathbb{Z}}          % ganze Zahlen
\newcommand{\R}       {\mathbb{R}}          % reelle Zahlen
\newcommand{\Prob}    {\mathrm{P}}          % Wahrscheinlichkeit
\newcommand{\inter}   {\cap}                % Schnittmenge
\newcommand{\union}   {\cup}                % Vereinigung
\newcommand{\Oh}      {\mathcal{O}}         % O-Notation (Landau-Symbole)
\newcommand{\mycite}[1]{\textcolor{tumgreen}{[#1]}}

\newenvironment{changemargin}[2]{%
    \begin{list}{}{%
            \setlength{\topsep}{0pt}%
            \setlength{\leftmargin}{#1}%
            \setlength{\rightmargin}{#2}%
            \setlength{\listparindent}{\parindent}%
        \setlength{\itemindent}{\parindent}%
            \setlength{\parsep}{\parskip}%
        }%
\item[]}{\end{list}}


\usetikzlibrary{shapes.geometric}
\pgfdeclarelayer{background}
\pgfdeclarelayer{midground}
\pgfsetlayers{background,midground,main}
\tikzstyle{vertex}=[circle,draw,fill=blue!25,minimum size=20pt,inner sep=0pt]
\tikzstyle{selected vertex} = [vertex, fill=red!50]
\tikzstyle{small vertex} = [vertex, minimum size=12pt]
\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}
\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}
%Inhaltsverzeichnis zu Begin von jedem Abschnitt einblenden?
%\AtBeginSection[]{
%  \begin{frame}
%    \frametitle{Outline}
%    \tableofcontents[currentsection]
%  \end{frame}
%}
%\AtBeginSection[]{
%   \begin{frame}[plain]
%       \begin{center} \LARGE\insertsectionhead \end{center}
%   \end{frame}
%}

\begin{document}

\begin{frame}
    \titlepage
\end{frame}

% Inhaltsverzeichnis
%\begin{frame}
%  \frametitle{Inhalt}
%  \tableofcontents
%\end{frame}

\begin{frame}
    \frametitle{Grundlegendes}
    \begin{itemize}
        \item<1-> Graph $G$, Knotenmenge $V$, Kantenmenge $E$
        \item<1-> $G = (V, E)$
        \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
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Grundlegendes}
    \begin{columns}[T]
        \begin{column}{.5\textwidth}
            \begin{itemize}
                \item<2> Artikulationsknoten \\(\emph{cut vertex})
                \item<3> Block
                \item<4> Pfad
                \item<5> Zyklus
                \item<6> Facette (\emph{face})
                \item<7> Bipartitheit
            \end{itemize}
        \end{column}
        \begin{column}{.5\textwidth}
            \begin{figure}
                \begin{tikzpicture}[auto]
                    \useasboundingbox (-2, 0) rectangle (7,7);

                    \foreach \pos/\name in {{(0,0)/a}, {(0,1.5)/b}, {(2,0)/c},{(2,1.5)/d},
                    {(-2,2.5)/e},
                    {(0,3.5)/f}, {(2,3.5)/g}, {(0,5)/h},{(2,5)/i},
                    {(1,6.5)/k}}
                    \node[vertex] (\name) at \pos {};

                    \foreach \source/ \dest in {a/b, a/c, c/d, b/d,
                        b/e, e/f,
                    f/g, f/h, h/i, g/i, h/k}
                    \path[edge] (\source) -- (\dest);
                    \path[edge] (g) .. controls (3, 5.5) .. (k);

                    \foreach \vertex / \fr in {e/2,
                        f/3, g/3, h/3, i/3, k/3,
                        a/4, b/4, e/4, f/4,
                        a/5, b/5, c/5, d/5,
                        a/7, d/7, e/7, g/7, h/7
                    }
                    \path<\fr> node[selected vertex] at (\vertex) {};

                    \begin{pgfonlayer}{background}
                        \foreach \source / \dest / \fr in {
                            f/g/3, f/h/3, h/i/3, g/i/3, h/k/3,
                            a/b/4, b/e/4, e/f/4,
                            a/b/5, b/d/5, c/d/5, c/a/5
                        }
                        \path<\fr>[selected edge] (\source) -- (\dest);
                        \path<3>[selected edge] (g) .. controls (3, 5.5) .. (k);

                        \fill<6>[red!50] (a.center) -- (b.center) -- (d.center) -- (c.center);
                        \draw<6> (1, 0.75) node {f};
                    \end{pgfonlayer}
                \end{tikzpicture}
            \end{figure}
            \vspace{1em}
        \end{column}
    \end{columns}
\end{frame}

\begin{frame}
    \frametitle{Planarität}
    \begin{itemize}
        \item \alert{offene Jordankurve}
            \vspace{0.2em}
            \begin{figure}
                \begin{tikzpicture}
                    \draw (0,0) .. controls (1,1) and (4,0.5) .. (3,1);

                    \draw (4,0) .. controls (5,1) .. (6,0.3) .. controls (7,0.5) .. (7,1);
                    \draw (6,0.3) .. controls (8,-0.5) and (3,0) .. (6,0.3);
                \end{tikzpicture}
            \end{figure}
            \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
            \vspace{2em}
        \item<2-> \alert{planar}: Keine sich überschneidenden Kurven
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Charakterisierung}

    \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.
        \end{itemize}
    \end{theorem}

    \begin{figure}
        \begin{tikzpicture}[auto]
            \foreach \pos/ \name in {{(0,1)/a}, {(1,1)/b}, {(2,1)/c},{(0,2)/d},{(1,2)/e},{(2,2)/f},
            {(4.164,1)/g}, {(5.464,1)/h}, {(5.626,1.986)/i},{(4.814,2.75)/j},{(4,1.986)/k}}
            \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,
                g/h, g/i, g/j, g/k,
                h/i, h/j, h/k,
                i/j, i/k,
            j/k}
            \path[edge] (\source) -- (\dest);

            \node at (1,0) {$K_{3,3}$};
            \node at (4.814,0) {$K_5$};
        \end{tikzpicture}
    \end{figure}
\end{frame}

\begin{frame}
    \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> Knoten von \alert{Grad 1} entfernen
                \item<4,5> Knoten von \alert{Grad 2} durch Kanten ersetzen
            \end{itemize}

            \vspace{1.5em}
            \uncover<5>{Teilgraphen sind\ldots}
            \begin{itemize}
                \item<5> planar wenn $|E| < 9$ oder $|V| < 5$
                \item<5> nicht planar wenn $|E| > 3|V| - 6$
            \end{itemize}
        \end{column}
        \begin{column}{.4\textwidth}
            \begin{figure}
                \begin{tikzpicture}[auto]
                    \useasboundingbox (-1, -1) rectangle (7,7);

                    \node<1>[vertex] (t) at (2,5) {};
                    \node<1>[vertex] (s) at (2,2) {};
                    \path<1>[edge] (t) .. controls (1,6) and (3,6) .. (t);
                    \path<1>[edge] (s) .. controls (1.5,3.5) .. (t);
                    \path<1>[edge] (s) .. controls (2.5,3.5) .. (t);

                    \foreach \pos/\name in {{(0,0)/a}, {(0,2)/b}, {(2,0)/c},{(2,2)/d},
                    {(1,1)/e}}
                    \node<2>[vertex] (\name) at \pos {};

                    \foreach \pos/\name in {{(0,4)/f}, {(2,4)/g}, {(3,5)/h},{(2,6)/i},
                    {(0,6)/j}}
                    \node<2>[vertex, fill=red!25] (\name) at \pos {};

                    \foreach \source/ \dest in {a/b, a/c, c/d, b/d,
                    a/e, e/d, f/g, g/h, h/i, h/j, g/i}
                    \path<2>[edge] (\source) -- (\dest);

                    \foreach \pos/\name in {{(0,0)/a}, {(0,1.5)/b}, {(2,0)/c},{(2,1.5)/d}}
                    \node<3,5>[vertex] (\name) at \pos {};

                    \foreach \pos/\name in {{(0,3.5)/f}, {(2,3.5)/g}, {(0,5)/h},{(2,5)/i},
                    {(1,6.5)/k}}
                    \node<3,5>[vertex, fill=red!25] (\name) at \pos {};

                    \node<3,5>[vertex, fill=green!25] (e) at (-1,2.5) {};

                    \foreach \source/ \dest in {a/b, a/c, c/d, b/d,
                        b/e, e/f,
                    f/g, f/h, h/i, g/i, h/k}
                    \path<3,5>[edge] (\source) -- (\dest);
                    \path<3,5>[edge] (g) .. controls (3, 5.5) .. (k);

                    \foreach \pos/\name in {{(0,3)/a}, {(0,5)/b}, {(2,3)/c},{(2,5)/d}}
                    \node<4>[vertex] (\name) at \pos {};
                    \node<4>[vertex, fill=red!25] (e) at (1, 4) {};

                    \foreach \source/ \dest in {a/b, a/c, c/d, b/d,
                    a/e, e/d}
                    \path<4>[edge] (\source) -- (\dest);
                \end{tikzpicture}
            \end{figure}
            \vspace{1em}
        \end{column}
    \end{columns}
\end{frame}

\begin{frame}
    \frametitle{Algorithmen}
    \begin{itemize}
        \item \alert{Knotenbasiert}
            \begin{itemize}
                \item Ein Graph bleibt planar wenn man einzelne Knoten entfernt
                \item Prozess kann umgekehrt werden
            \end{itemize}
            \vspace{2em}
        \item \alert{Kreisbasiert}
            \begin{itemize}
                \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
            \end{itemize}
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{LR-Algorithmus}

    \begin{itemize}
        \item Kreisbasiert
        \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]
        \begin{column}{.35\textwidth}
            \begin{itemize}
                \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}
        \begin{column}{.65\textwidth}
            \begin{figure}
                \begin{tikzpicture}[auto, scale=0.7]
                    \useasboundingbox (-2,0) rectangle (6,10);

                    \foreach \pos/\name in {{(0,0)/a},{(0,2)/b},{(-1,4)/c},{(-2,6)/d},{(0,6)/e},
                    {(-1,8)/f}, {(1,8)/g},
                    {(3,4)/h}, {(5,6)/i}, {(4,8)/j},{(6,8)/k}}
                    \node[vertex] (\name) at \pos {};

                    \path<1> node[selected vertex] at (a) {$r$};

                    \foreach \pos/\name in {{(0,2)/2},{(-1,4)/3},{(-2,6)/4},{(0,6)/5},
                    {(-1,8)/6}, {(1,8)/7},
                    {(3,4)/8}, {(5,6)/9}, {(4,8)/10},{(6,8)/11}}
                    \path<2> node[vertex] at \pos {$\name$};
                    \path<2> node[selected vertex] at (0,0) {$1$};

                    \foreach \source/ \dest in {a/b, b/c, c/d, c/e, e/f, e/g,
                    b/h, h/i, i/j, i/k}
                    \path[tree edge] (\source) -- (\dest);

                    \foreach \source/\dest/\ctrl in {{f/b/(2.5, 9.2)}, {g/c/(0.5,5)}, {d/a/(-2,2)},
                    {j/b/(4.5, 3)}, {k/b/(6,3)}}
                    \path[back edge] (\source) .. controls \ctrl .. (\dest);
                \end{tikzpicture}
            \end{figure}
            \vspace{1em}
        \end{column}
    \end{columns}
\end{frame}

\begin{frame}
    \frametitle{Beispiel}

    \begin{figure}
        \begin{tikzpicture}[auto, scale=1.3]
            \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<1>[edge] (\source) -- (\dest);

            \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<2->[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<1>[edge] (\source) -- (\dest);

            \foreach \source/ \dest in {f/b, k/c, k/i, j/a, g/d, m/e, n/l, n/a}
            \path<2>[back edge] (\source) -- (\dest);

            \foreach \source/ \dest in {f/b, m/e, n/a}
            \path<3>[left edge] (\source) -- (\dest);

            \foreach \source/ \dest in {k/c, k/i, j/a, g/d, n/l}
            \path<3>[right edge] (\source) -- (\dest);

            \draw<2> (0,0) node {DFS};
            \draw<3> (0,0) node {LR-Zerlegung};
        \end{tikzpicture}
    \end{figure}
\end{frame}

\begin{frame}
    \frametitle{LR-Zerlegung}

    \begin{itemize}
        \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 \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}
    \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:
        \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}
    \end{definition}

    \begin{center}
        \begin{figure}
            \begin{tikzpicture}[auto, scale=0.5]
                \useasboundingbox (-4, 2) 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) {};
                \node[small vertex] (x) at (2,8) {};

                \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,2) -- (u);

                \draw[left edge] (w) .. controls (-2, 5) .. (u);
                \draw[right edge] (x) .. controls (2, 5) .. (u);
                \draw[back edge] (w) .. controls (-3, 5) .. (0,2);
                \draw[back edge] (x) .. controls (3, 5) .. (0,2);
            \end{tikzpicture}
        \end{figure}
    \end{center}
\end{frame}

\begin{frame}
    \frametitle{LR-Zerlegung}

    \begin{theorem}
        Ein Graph ist genau dann planar, wenn er eine \alert{LR-Zerlegung} zulässt.
    \end{theorem}

    \vspace{2em}

    \begin{itemize}
        \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
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Verschachtelung}

    \begin{block}{Beobachtung}
        Die Baumkante $e_1$ muss außerhalb von Baumkante sein $e_2$ wenn
        \begin{itemize}
            \item $lowpt(e_1) < lowpt(e_2)$
        \end{itemize}
        oder
        \begin{itemize}
            \item $lowpt(e_1) = lowpt(e_2)$ und $e_2$ eine Sehne besitzt
        \end{itemize}
    \end{block}
    \begin{center}
        \begin{figure}
            \begin{tikzpicture}[auto]
                \useasboundingbox (-2, 0.5) rectangle (7, 5);

                \draw[edge] (0,1) -- (0,3);
                \draw[edge] (-1.5,4) -- (0,3) node[midway, above] {$e_1$};
                \draw[edge] (1.5,4) -- (0,3) node[midway, above] {$e_2$};

                \draw[back edge, rounded corners] (-1.5,4) .. controls (4,6) and (1,1) .. (0,1);
                \draw[back edge] (1.5,4) .. controls (0.5,2) .. (0,2);


                \draw[edge] (4.5,1) -- (4.5,3);
                \draw[edge] (3,4) -- (4.5,3) node[midway, above] {$e_1$};
                \draw[edge] (6,4) -- (4.5,3) node[midway, above] {$e_2$};

                \draw[back edge, rounded corners] (3,4) .. controls (8.5,6) and (5.5,1) .. (4.5,1);
                \draw[back edge] (6,4) .. controls (5,2) .. (4.5,2);
                \draw[back edge] (6,4) .. controls (5.5,2) .. (4.5,1);
            \end{tikzpicture}
        \end{figure}
    \end{center}
\end{frame}

\begin{frame}
    \frametitle{Verschachtelung}
    \begin{columns}[T]
        \begin{column}{.5\textwidth}
            \begin{figure}
                \begin{tikzpicture}[auto, scale=0.5]
                    \useasboundingbox (-5, 0) rectangle (5, 8);

                    \node[vertex] (u) at (0,0) {$u$};
                    \node[vertex] (v) at (0,3) {$v$};
                    \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) 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}
        \end{column}
        \begin{column}{.5\textwidth}
            \begin{figure}
                \begin{tikzpicture}[auto, scale=0.5]
                    \useasboundingbox (-5, 0) rectangle (5, 8);

                    \node[vertex] (u) at (0,0) {$u$};
                    \node[vertex] (v) at (0,3) {$v$};
                    \node[small vertex] (w) at (-3,6) {};
                    \node[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{figure}
        \end{column}
    \end{columns}
\end{frame}

\begin{frame}
    \frametitle{Verschachtelung}

    \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),\\
            &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.
    \end{definition}

    \alert{$L(e)$} bezeichnet die linken eingehenden Rückwärtskanten deren Kreise sich $e$ teilen.
\end{frame}

\begin{frame}
    \frametitle{Planarisierung}

    \begin{block}{Lemma}
        Eine \alert{LR-Ordnung} stellt eine Planarisierung einer \alert{LR-Zerlegung} dar.
    \end{block}
    \vspace{2em}

    \begin{block}{Beweisidee}
        Beweis durch 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}
    \frametitle{Algorithmus}

    \begin{itemize}
        \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 Gabelungen
            \end{itemize}
        \item Können alle Bedingungen gleichzeitig erfüllt werden?
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Algorithmus}

    \begin{columns}[T]
        \begin{column}{.33\textwidth}
            \begin{figure}
                \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}
            \end{figure}
        \end{column}
        \begin{column}{.33\textwidth}
            \begin{figure}
                \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}
            \end{figure}
        \end{column}
        \begin{column}{.33\textwidth}
            \begin{figure}
                \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}
            \end{figure}
        \end{column}
    \end{columns}
\end{frame}

\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:
        \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\}$
        \end{itemize}
    \end{block}

    \alert{$C(b)$} bezeichnet Knoten auf dem Zyklus, der durch $b$ geschlossen wird.
\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}
\end{frame}

\begin{frame}
    \frametitle{Constraintgraph}

    \begin{figure}
        \begin{tikzpicture}[auto, scale=1.3]
            \useasboundingbox (-4,1) rectangle (4,6);

            \foreach \pos/\name/\ctn in {{(0,1)/a/1},{(0,2)/b/2},{(1,3)/c/3},{(0.75,4)/d/4},{(-0.5,4.5)/e/5},
            {(-1.5,3.5)/f/6}, {(1.25,5.25)/g/7},
            {(0,5.5)/h/8}, {(2.5,6)/i/9}, {(4,5)/j/10},{(2.5,4.5)/k/11},
            {(-2,6)/l/12}, {(-2.5,5)/m/13}, {(-4,5)/n/14}}
            \node<1>[vertex, minimum size=15pt] (\name) at \pos {$\ctn$};

            \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<1>[tree edge] (\source) -- (\dest);

            \foreach \source/ \dest in {f/b, m/e, n/a}
            \path<1>[left edge] (\source) -- (\dest);

            \foreach \source/ \dest in {k/c, k/i, j/a, g/d, n/l}
            \path<1>[right edge] (\source) -- (\dest);

            \begin{pgfonlayer}{background}
                \foreach \pos/\name/\ctn in {{(0,1)/a/1},{(0,2)/b/2},{(1,3)/c/3},{(0.75,4)/d/4},{(-0.5,4.5)/e/5},
                {(-1.5,3.5)/f/6}, {(1.25,5.25)/g/7},
                {(0,5.5)/h/8}, {(2.5,6)/i/9}, {(4,5)/j/10},{(2.5,4.5)/k/11},
                {(-2,6)/l/12}, {(-2.5,5)/m/13}, {(-4,5)/n/14}}
                \node<2->[vertex, minimum size=15pt, opacity=0.2] (\name) at \pos {$\ctn$};

                \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<2->[tree edge, opacity=0.35] (\source) -- (\dest);

                \foreach \source/ \dest / \name in {f/b, m/e, n/a}
                \path<2->[left edge, opacity=0.35] (\source) -- (\dest)
                node[midway, anchor=center] (\source\dest) {};

                \foreach \source/ \dest in {k/c, k/i, j/a, g/d, n/l}
                \path<2->[right edge, opacity=0.35] (\source) -- (\dest)
                node[midway, anchor=center] (\source\dest) {};
            \end{pgfonlayer}

            \foreach \source/ \dest in {f/b, m/e, n/a}
            \node<2->[fill=blue,minimum size=10pt] at (\source\dest) {};

            \foreach \source/ \dest in {k/c, k/i, j/a, g/d, n/l}
            \node<2->[fill=red,minimum size=10pt] at (\source\dest) {};

            \begin{pgfonlayer}{midground}
                \path<3->[edge, ultra thick] (kc.center) -- (ki.center) node[midway] {s};
                \path<4->[edge, ultra thick] (me.center) -- (nl.center) node[midway, above] {v};
                \path<5->[edge, ultra thick] (me.center) -- (kc.center) node[midway] {v};
                \path<5->[edge, ultra thick] (fb.center) -- (kc.center) node[midway] {v};
            \end{pgfonlayer}
        \end{tikzpicture}
    \end{figure}
\end{frame}

\begin{frame}
    \frametitle{LR-Algorithmus}

    \begin{block}{Algorithmus}
        \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 polynomieller Aufwand
        \item Kann in $\Oh(n)$ implementiert werden indem der Graph nicht explizit erzeugt wird
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Q \& A}

    \begin{center} \LARGE Danke für die Aufmerksamkeit!\end{center}
    \vspace{1em}
    \begin{center} \LARGE Fragen?\end{center}
\end{frame}

\begin{frame}[plain]
    \begin{center} \LARGE Backup\end{center}
\end{frame}

\begin{frame}
    \frametitle{Knotenbasierte Algorithmen}
    \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}

\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}