Institut für Theoretische Informatik, Algorithmik

Algorithmen für planare Graphen

Sommersemester 2014

Allgemeines

  • Übungsleiter: Dr. Andreas Gemsa
  • Vorlesung: Dienstags, 14:00–15:30, Hörsaal II - Gebäude 30.41 - Chemie Flachbau und Mittwochs, 14:00–15:30, Mittlerer Hörsaal - Gebäude 10.91 - Maschinenbau (im Schnitt eine Vorlesung pro Woche)
  • Übung: zusätzlich wird an einigen Vorlesungsterminen eine Übung stattfinden

Ein planarer Graph ist ein Graph, der in der Ebene gezeichnet werden, ohne dass die Kanten sich kreuzen. Planare Graphen haben viele schöne Eigenschaften, die benutzt werden können um für zahlreiche Probleme besonders einfache, schnelle und schöne Algorithmen zu entwerfen. Oft können sogar Probleme, die auf allgemeinen Graphen (NP-)schwer sind auf planaren Graphen sehr effizient gelöst werden. Einige dieser Probleme und Algorithmen zu ihrer Lösung werden in dieser Vorlesung vorgestellt.

Neueste Meldungen

Zur Frage welcher Beweis für Kuratowskis Theorem gekonnt werden muss (der aus der VL oder der im Skript steht): Beide sind akzeptabel. Wer den Beweis aus der VL noch einmal genauer nachvollziehen will dem hilft eventuell ein dieser Link [PDF].
Zusatzübung

Die Abstimmung wurde beendet und das Ergebnis ist das Folgende:

Datum: Mittwoch, 06.08

Raum: 301, Gebäude 50.34 (ACHTUNG: ANDERER HÖRSAAL ALS SONST)

Damit wir Themen für die Übung haben bitte ich euch mir (Andreas) Vorschläge oder Fragen rechtzeitig zu schicken. Ansonsten wird diese Zusatzübung eher kurz ausfallen. Ich bin auf eure Vorschläge angewiesen.

Prüfungen:

Es werden Prüfungstermine an den folgenden Tagen angeboten:

14. August, 19. September, 02. Oktober, 17. Oktober

Anmeldung: Die Anmeldung erfolgt per e-Mail an Lilian Beckert nach dem „first come, first served“-Prinzip.

Wichtig: Die Anmeldung muss bis spätestens 3 Wochen vor dem Prüfungstermin erfolgen.

Vorlesung wurde verlegt:

Dienstags: Hörsaal II - Gebäude 30.41 - Chemie Flachbau
Mittwochs: Mittlerer Hörsaal - Gebäude 10.91 - Maschinenbau

Termine

Di Mi
15.04. Vorlesung 16.04. Vorlesung Folien zum Satz von Kuratowski
22.04. Übung Folien 23.04. Vorlesung Folien zu PQ-Bäumen und Planaritätstest
29.04. Vorlesung Folien zur Färbung 30.04. -
06.05. Übung Folien 07.05. -
13.05. Vorlesung, Planar separator theorem (Skript, Kap 4) 14.05. Vorlesung, Planar separator theorem
20.05. Übung Folien 21.05. Vorlesung, Maximum matching (Skript, Kap 5)
27.05. Vorlesung, Maximum cut (Skript, Kap 6) 28.05. -
03.06. Übung 04.06. Vorlesung
10.06. Vorlesung 11.06. -
17.06. - 18.06. -
24.06. Vorlesung, Maximum flow in directed graphs ([E10]) 25.06. Vorlesung, Maximum flow in directed graphs
01.07. - 02.07. -
08.07. Vorlesung 09.07. Vorlesung, Folien zum Planaritätstest
15.07. Übung 16.07. Übung Verschoben. Siehe Ankündigung

Folien und Skripte

Übungen

Es wird regelmäßig Übungsblätter geben, diese werden teilweise im Rahmen der Übungstermine besprochen.

Übungsblatt 1

Übungsblatt 2

Übungsblatt 3

Übungsblatt 4

Übungsblatt 5

Literatur

Literatur zu Listenfärbung
[Die10] Reinhard Diestel, Graph Theory, Springer, 2010.
[Mat12] Martin Matkovic, Bachelorarbeit über Listenfärben in Graphen, 2012.
Bücher zu planaren Graphen
[Aig84] Martin Aigner. Graphentheorie: Entwicklung aus dem 4-Farben-Problem. Teubner, 1984.
[BM76] John A. Bondy and Uppaluri R.S. Murty. Graph theory with applications. North-Holland, 1976.
[Jun94] Dieter Jungnickel. Graphen, Netzwerke und Algorithmen. BI-Wissenschaftsverlag, 1994.
[NC88] Takao Nishizeki and Norishige Chiba. Planar Graphs: Theory and Algorithms, volume 32 of Annals of Discrete Mathematics. North-Holland, 1988. ISBN 0-444-70212-1.
[TS92] K. Thulasiraman und M.N.S. Swamy. Graphs: Theory and Algorithms. Wiley, 1992.
Artikel zu ausgewählten Themen
[BM04] John M. Boyer and Wendy J. Myrvold, On the Cutting Edge: Simplified O(n) Planarity by Edge Addition. Theory Ser. B. 70 (1997), 2–44.
[RSST97] N. Robertson, D. P. Sanders, P. D. Seymour and R. Thomas, The four colour theorem, J. Combin. Theory Ser. B. 70 (1997), 2–44.
[T95] N. Robertson, D. P. Sanders, P. D. Seymour and R. Thomas, The four colour theorem, electronic resource
[T95b] N. Robertson, D. P. Sanders, P. D. Seymour and R. Thomas, The four colour theorem, unpublished manuscript and computer program
[Tor] Arne-Michael Törsel, Analyse und Implementation des Boyer-Myrvold Algorithmus zur Einbettung planarer Graphen. Diplomarbeit an der Fachhochschule Stralsaund, Fachbereich Wirtschaft, 2002?
[WW95] Dorothea Wagner, Karsten Weihe A linear-time algorithm for edge-disjoint paths in planar graphs. Combinatorica, Volume 15, Number 1/March, 1995
[I06] Alon Itai Linear time restricted union find. Manuscript 2006
[E10] Jeff Erickson Maximum flows and parametric shortest paths in planar graphs. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms, 794-804, 2010.
Sonstige Bücher
[A99] Giorgio Ausiello et al. Complexity and Approximation. Springer Verlag, 1999.
[CLR01] T. H. Cormen, C. E. Leiserson, R. L. Rivest u.a. Introduction to Algorithms / Algorithmen -- eine Einführung. MIT Press, 1990-2001 / Oldenburg 2004.
[dBETT99] Giuseppe Di Battista, Peter Eades, Roberto Tamassia, and Ioannis G. Tollis Graph Drawing : Algorithms for the Visualization of Graphs. Prentice Hall, 1999.
[GJ79] Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. WH Freeman & Co Ltd, 1979.
[OW90] Thomas Ottmann und Peter Widmayer. Algorithmen und Datenstrukturen. Spektrum, Akad. Verl., 1990-2002.
[S01] Uwe Schöning. Algorithmik. Spektrum Akademischer Verlag, 2001.