\documentstyle[a4wide,german]{article}
\pagestyle{empty}

\begin{document}

\section{Graphentheoretische Grundlagen (Euler, Kuratowski)}

\section{Graphentheoretische Grundlagen (Dualit\"at)}

\section{Planarit\"atstest (Vertex-Addition)}
Es gibt zwei klassische Verfahren, um in linearer Zeit zu entscheiden,
on ein Graph planar ist. Dies ist zum einen der
``path addition'' Algorithmus von Hopcoft und Tarjan und zum anderen
der ``vertex addition'' Algorithmus, der auf Lempel, Even und
Cederbaum zur\"uckgeht.
Zu jedem der beiden Ans\"atze wurden auch Verfahren entwickelt, die
im Falle der Planarit\"at eine planare Einbettung berechnen bzw.
im umgekehrten Falle einen Kuratowski-Teilgraphen als Beweis f\"ur die
Nicht-Planarit\"at ermitteln.

Im Seminar soll der ``vertex addition'' Algorithmus ausf\"uhrlich
besprochen werden. Eine sehr gute Beschreibung, die das Prinzip und die
Korrektheit des Verfahrens erkl\"art, findet sich in \cite{e79}.
Ein wesentlicher Punkt ist hierbei die Betrachtung der Knoten in einer
durch eine sogenannte $st$-Nummerierung gegebenen Reihenfolge. 
In \cite{nc883} wird genauer auf Implementierungsdetails eingegangen und
auch die Berechnung einer planaren Einbettung beschrieben 
(siehe auch \cite{cn85}).
Schlie\3lich wird in \cite{hmn96} eine Erweiterung des Algorithms zur
ggf. erforderlichen Bestimmung eines Kuratowski-Untergraphen
dargestellt.
Wichtig f\"ur eine Realisierung in linearer Zeit ist die Datenstrukur der
sogenannten $PQ$-B\"aume und die effiziente Berechnung einer $st$-Nummerierung.

\section{Planarit\"atstest (Einbettung, Kuratowski-Teilgraphen)}

Es gibt zwei klassische Verfahren, um in linearer Zeit zu entscheiden,
on ein Graph planar ist. Dies ist zum einen der
``path addition'' Algorithmus von Hopcoft und Tarjan und zum anderen
der ``vertex addition'' Algorithmus, der auf Lempel, Even und
Cederbaum zur\"uckgeht.
Zu jedem der beiden Ans\"atze wurden auch Verfahren entwickelt, die
im Falle der Planarit\"at eine planare Einbettung berechnen bzw.
im umgekehrten Falle einen Kuratowski-Teilgraphen als Beweis f\"ur die
Nicht-Planarit\"at ermitteln.

Im Seminar soll der ``vertex addition'' Algorithmus ausf\"uhrlich
besprochen werden. Eine sehr gute Beschreibung, die das Prinzip und die
Korrektheit des Verfahrens erkl\"art, findet sich in \cite{e79}.
Ein wesentlicher Punkt ist hierbei die Betrachtung der Knoten in einer
durch eine sogenannte $st$-Nummerierung gegebenen Reihenfolge. 
In \cite{nc883} wird genauer auf Implementierungsdetails eingegangen und
auch die Berechnung einer planaren Einbettung beschrieben 
(siehe auch \cite{cn85}).
Schlie\3lich wird in \cite{hmn96} eine Erweiterung des Algorithms zur
ggf. erforderlichen Bestimmung eines Kuratowski-Untergraphen
dargestellt.
Wichtig f\"ur eine Realisierung in linearer Zeit ist die Datenstrukur der
sogenannten $PQ$-B\"aume und die effiziente Berechnung einer $st$-Nummerierung.

\section{Zeichnen Planarer Graphen (konvex)}

\section{Zeichnen Planarer Graphen (Gitter)}

\section{Knotenf\"arbung}
Das Problem die Knoten eines Graphen mit einer minimalen Anzahl von Farben 
so zu f\"arben, da\3 keine durch eine Kante verbundenen Knoten dieselbe
Farbe haben, ist bis heute nicht effizient l\"osbar. 
F\"ur planare Graphen, d.h. Graphen die man ohne Kanten\"uberschneidungen
in der Ebene zeichnen kann, ist jedoch bekannt, da\3 vier Farben in jedem Fall
ausreichen. Der Beweis ist aber sehr kompliziert und der quadratische
Algorithmus nicht praktikabel.

Einen planaren Graphen mit f\"unf Farben zu f\"arben ist dagegen sehr
effizient in Linearzeit m\"oglich. Der Vortrag soll auf der
Grundlage von \cite{nc885} solche Verfahren vorstellen.
Sie lassen sich grob in zwei Ans\"atze unterscheiden.
Bei sequentiellen Algorithmen wird ein bestimmter Knoten ausgew\"ahlt und
mit einer Transformation aus dem Graphen entfernt. Wesentlich f\"ur die
lineare Laufzeit ist, da\3 diese Transformationen effizient durchf\"uhrbar
sind. Bei den sogenannten Batch-Processing-Algorithmen besteht der
entscheidende Schritt darin, da\3 in jeder Phase
ein konstanter Bruchteil der Knoten entfernt werden kann. 

Grundlage f\"ur die jeweiligen Garantien bilden interessante kombinatorische
Eigenschaften planaren Graphen, die in \cite{f84} noch etwas genauer
betrachtet werden.

\section{Unabh\"angige Knotenmengen}
Die maximale Teilmenge der Knotenmenge eines Graphen zu berechnen,
so da\3 es zwischen diesen Knoten keine Kante gibt, ist ein 
${\cal NP}$-hartes Problem. F\"ur allgemeine Graphen gibt es unter der
Annahme ${\cal P} \not= {\cal NP}$ nicht einmal einen 
Approximationsalgorithmus mit konstantem Approximationsfaktor.
F\"ur planarer Graphen ergibt sich ein solcher Approximationsalgorithmus
dagegen sofort aus der 4-F\"arbbarkeit. 
In \cite{nc887} wird jedoch ein qualitativ wesentlich besserer Algorithmus
vorgestellt: er liefert in Zeit ${\cal O}(n \log n)$ eine unabh\"angige
Knotenmenge, die mindestens halb so gro\3 ist wie eine maximale
unabh\"angige Knotenmenge. 
Es geht jedoch noch besser. Auf planaren Graphen gibt es sogar ein
sogenanntes Approximationsschema, d.h. eine Familie von Algorithmen, so
da\3 es f\"ur jedes $\epsilon > 0$ einen Algorithmus gibt, der eine
maximale unabh\"angige Knotenmenge bis auf den Faktor $1 - \epsilon$
approximiert.
Nach einer kurzen Einf\"uhrung des Begriff des Approximationsschemas 
soll ein solches kurz vorgestellt werden.

\section{Isomorphismustest}

\section{Aufz\"ahlen von Teilgraphen}

\section{Planare Seperatoren}
``Divide-and-conquer''-Ans\"atze haben sich bei der L\"osung vieler
kombinatorischer Problme als n\"utzlich erwiesen. Dabei mu\3 das
Ausgangsproblem in kleinere Teilprobleme zerlegt werden k\"onnen,
die dann rekursiv mit der selben Methode gel\"ost werden.
F\"ur Probleme auf Graphen stellen Seperatoren einen
geeigneten Teilungsbegriff dar.
Ein Seperator ist eine Teilmenge der Knotenmenge, nach deren Entfernung
der Graph in relativ kleine Teilgraphen zerf\"allt.
Lipton und Tarjan \cite{lt79} wiesen 1979 erstmals die Existenz solcher
Seperatoren in planaren Graphen nach und zeigten wie man sie effizient
berechnet.
Eine Kurzdarstellung dieses Resultats findet sich auch in \cite{berlin96}.
Die Verwendung planarer Seperatoren zur L\"osung verschiedener 
Graphenprobleme wird in \cite{lt80} beschrieben.
Beispielhaft soll die Konstruktion eines Approximationsschemas f\"ur
unabh\"angige Knotenmengen vorgestellt werden, das auch f\"ur den
nachfolgenden Vortrags relevant ist.

\section{\"Uberdeckende Knotenmengen}
Ein klassisches Problem der Graphentheorie ist die Bestimmung einer
minimalen Teilmenge $C \subseteq V$ der Knotenmenge, 
so da\3 jede Kante des Graphen
zu mindestens einem der Knoten dieser Teilmenge inzident ist.
Da dieses Problem ${\cal NP}$-hart ist, greift man auf 
Approximationsalgorithmen zur\"uck. Es gibt sehr einfache Algorithmen,
die \"Uberdeckenden Knotenmengen finden, die h\"ochstens doppelt so
gro\3 wie die minimale \"Uberdeckende Knotenmenge sind.
Bis heute ist f\"ur allgemeine Graphen auch kein wesentlich besseres
Ergebnis bekannt.

F\"ur planare Graphen sieht dies anders aus. In \cite{be82} wird
zun\"achst ein Algorithmus vorgestellt, der im allgemeinen ebenfalls
eine 2-Approximation liefert, auf planaren Graphen jedoch eine G\"ute
von $\frac{5}{3}$ garantiert. Seine Laufzeit ist linear.
Die Situation ist jedoch noch viel besser. Es gibt ein sogenanntes
Approximationsschema, d.h. eine Familie von Algorithmen, so da\3
es f\"ur jedes $\epsilon > 1$ einen Approximationsalgorithmus gibt,
der eine L\"osung produziert, die nicht weiter als um einen Faktor
$\epsilon$ von der optimalen L\"osung entfernt ist.
Dieses Schema wird aus einem bekannten Schema f\"ur das Problem
der maximalen unabh\"angigen Knotenmengen (siehe fr\"uherer Vortrag)
konstruiert.

\section{Maximale Schnitte}

\section{Kantendisjunkte $(s,t)$-Pfade}

\begin{thebibliography}{99}
\bibitem{e79} S. Even: 
              {\sl Graph Algorithms},
              Chapter 8: Testing Graph Planarity,
              Pitman 1979
\bibitem{nc883} T. Nishizeki, N. Chiba:
              {\sl Planar Graphs: Theory and Algorithms},
              Chapter 3: Planarity Testing and Embedding,
              North-Holland Mathematics Studies {\bf 140},
              Elsevier, 1988
\bibitem{hmn96} C. Hundack, K. Mehlhorn, S. N\"aher:
               {\sl A simple linear time algorithm for identifying
                Kuratowski subgraphs of non-planar graphs},
                Technischer Report, 1996
\bibitem{cn85} N. Chiba, T. Nishizeki:
               {\sl A Linear Algorithm for Embedding Planar Graphs
                Using $PQ$-Trees},
                Journal of Computer and System Sciences, {\bf 30},
                54--76, 1985
\bibitem{nc885} T. Nishizeki, N. Chiba:
              {\sl Planar Graphs: Theory and Algorithms},
              Chapter 5: Vertex-Coloring
              North-Holland Mathematics Studies {\bf 140},
              Elsevier, 1988
\bibitem{f84} G. N Frederickson:
              {\sl On Linear-Time Algorithms for Five-Coloring Planar Graphs},
              Information Processing Letters {\bf 19}, 1984, 219 -- 224
\bibitem{nc887} T. Nishizeki, N. Chiba:
              {\sl Planar Graphs: Theory and Algorithms},
              Chapter 7: Independent Vertex Sets
              North-Holland Mathematics Studies {\bf 140},
              Elsevier, 1988
\bibitem{berlin96} T. Emden-Weinert, St. Hougardy, B. Kreuter, H. J. Pr\"omel,
                   A. Steger: 
              {\sl Einf\"uhrung in Graphen und Algorithmen},
              Kapitel 8: Seperatoren,
              Skriptum, Humboldt-Universit\"at zu Berlin, 1996
\bibitem{lt79} R. J. Lipton, R. E. Tarjan:
              {\sl A Seperator Theorem for Planar Graphs},
              SIAM Journal on Applied Mathematics,
              Vol. {\bf 36}, No. 2, 177 -- 189, 1979
\bibitem{lt80} R. J. Lipton, R. E. Tarjan:
               {\sl Applications of a Planar Seperator Theorem},
               SIAM Journal on Computing, Vol. {\bf 9}, No. 3, 615 -- 617, 1980
\bibitem{be82} R. Bar-Yehuda, S. Even:
              {\sl On Approximating a Vertex Cover for Planar Graphs},
              14th Symp. on the Theory of Computing (STOC), 1982,
              303 -- 309
\end{thebibliography}

\end{document}
