Mercurial > latex
changeset 71:b06e34b08f9b
retab
| author | Markus Kaiser <markus.kaiser@in.tum.de> |
|---|---|
| date | Sun, 13 Jan 2013 22:26:02 +0100 |
| parents | 4e3e078f5338 |
| children | 11483d814594 |
| files | planarity/term_paper.bib planarity/term_paper.tex |
| diffstat | 2 files changed, 219 insertions(+), 219 deletions(-) [+] |
line wrap: on
line diff
--- a/planarity/term_paper.bib Fri Dec 14 22:42:15 2012 +0100 +++ b/planarity/term_paper.bib Sun Jan 13 22:26:02 2013 +0100 @@ -1,19 +1,19 @@ @unpublished{Bra09, - author = {Ulrik Brandes}, - 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} + author = {Ulrik Brandes}, + 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} } @incollection{Pat13, - author = {Maurizio Patrignani}, - editor = {Roberto Tamassia}, - booktitle = {Handbook of Graph Drawing and Visualization}, - title = {Planarity Testing and Embedding}, - year = {2013}, - publisher = {CRC Press}, - ee = {http://www.cs.brown.edu/~rt/gdhandbook/} + author = {Maurizio Patrignani}, + editor = {Roberto Tamassia}, + booktitle = {Handbook of Graph Drawing and Visualization}, + title = {Planarity Testing and Embedding}, + year = {2013}, + publisher = {CRC Press}, + ee = {http://www.cs.brown.edu/~rt/gdhandbook/} } @article{Kur30, @@ -47,7 +47,7 @@ title = {{On imbedding graphs in the sphere}}, volume = {114}, pages = {517--523}, - numpages = {7}, + numpages = {7}, year = {1961} } @@ -68,7 +68,7 @@ acmid = {321852}, publisher = {ACM}, address = {New York, NY, USA} -} +} @article{FMR06, author = {Hubert de Fraysseix and
--- a/planarity/term_paper.tex Fri Dec 14 22:42:15 2012 +0100 +++ b/planarity/term_paper.tex Sun Jan 13 22:26:02 2013 +0100 @@ -83,36 +83,36 @@ $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. \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] + \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}$.} + \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} @@ -128,88 +128,88 @@ 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 allein 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 $E = T \uplus B$ der Kanten in Baumkanten $T$ und Rückwärtskanten $B$. Der Graph $(V, T)$ ist maximal zyklenfrei, das Hinzufügen einer beliebigen Kante aus B erzeugt einen Zyklus. +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 $E = T \uplus B$ der Kanten in Baumkanten $T$ und Rückwärtskanten $B$. Der Graph $(V, T)$ ist maximal zyklenfrei, das Hinzufügen einer beliebigen Kante aus B erzeugt einen Zyklus. \begin{figure}[htb] - \centering - \hspace*{\fill} - \subfloat[Beispielgraph]{ + \centering + \hspace*{\fill} + \subfloat[Beispielgraph]{ \begin{tikzpicture}[scale=0.65] - \useasboundingbox (-4,0) rectangle (4,6); + \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); - + \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]{ + } + \centering + \hspace*{\fill} + \subfloat[DFS-Orientierung]{ \begin{tikzpicture}[scale=0.65] - \useasboundingbox (-4,0) rectangle (4,6); + \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); - + \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{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$. + \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} + \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\}$. @@ -217,28 +217,28 @@ 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); - + \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[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} + \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} @@ -252,38 +252,38 @@ \end{observation} \begin{figure}[htb] - \centering + \centering \begin{tikzpicture}[auto, scale=0.65] - \useasboundingbox (-4,0) rectangle (4,6); + \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); - + \path[tree edge] (\source) -- (\dest); + \foreach \source/ \dest in {f/b, m/e, n/a} - \path[left edge] (\source) -- (\dest); - + \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} + \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} + 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} @@ -309,55 +309,55 @@ \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} + \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 +\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) + &(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} + \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} @@ -376,77 +376,77 @@ 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} + 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} \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} + \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}).