Institut für Theoretische Informatik, Algorithmik

Algorithmen für planare Graphen

Sommersemester 2016

Allgemeines

  • Übungsleiter: Dr. Benjamin Niedermann
  • Vorlesung:
    • Montags, 15:45–17:15, Hörsaal -102 - Gebäude 50.34 - Informatik-Hauptgebäude
    • Dienstags, 14:00–15:30, Hörsaal II - Gebäude 30.41 - Chemie Flachbau
    • An einigen Vorlesungsterminen findet eine Übung statt.

Thema

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

  • 11. März: Homepage zur Vorlesung ist online.
  • 30. Mai: Prüfungstermine sind online.
  • 4. Juli: Vorlesung am 11. Juli findet nicht statt.
  • 11. Juli: Alle vorgesehenen Prüfungstermine sind vergeben (siehe Abschnitt Prüfungstermine)

Prüfungstermine

Alle vorgesehenen Prüfungstermine sind vergeben. Studierende, die noch keinen Prüfungstermin haben und sich noch dieses Semester prüfen lassen wollen, sollen sich bis zum 31. Juli per e-Mail an das Sekretariat (sekr [dash] wagner [at] ira [dot] uka [dot] de) wenden.

Eine Anmeldung zur Prüfung nach dem 31. Juli ist nicht mehr möglich. Weitere Prüfungstermine gibt es erst wieder, nachdem die Vorlesung ein erneutes Mal gehalten wurde.

Die Prüfungstermine in diesem Semester sind:

  • 15. Juli ausgebucht!
  • 18. August ausgebucht!
  • 15. September ausgebucht!
  • 6. Oktober ausgebucht!
  • 7. Oktober ausgebucht!

Anmeldung: Die Anmeldung erfolgt per e-Mail an das Sekretariat sekr [dash] wagner [at] ira [dot] uka [dot] de nach dem „first come, first served“-Prinzip.

Prüfung: Die Prüfung findet statt in Geb. 50.34, Raum 320.

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

Termine

Vorlesungen bzw. Übungen werden voraussichtlich an den folgenden Terminen stattfinden (Änderungen vorbehalten).

Mo Di
18.04. Vorlesung 19.04. Vorlesung Folien zum Satz von Kuratowski
25.04. Übung Übung1 26.04. -
02.05. Vorlesung 03.05. Vorlesung Folien zur Färbung
09.05. - 10.05. Vorlesung
16.05. - 17.05. Übung
23.05. Vorlesung 24.05. Vorlesung
30.05. Übung 31.05. Vorlesung
06.06. Vorlesung 07.06. Übung Übung4
13.06. Vorlesung 14.06. -
20.06. Vorlesung 21.06. Übung Übung5
27.06. Vorlesung 28.06. -
04.07. Vorlesung 05.07. Übung Übung6
11.07. Vorlesung findet nicht statt 12.07. -

Folien und Skripte

Übungen

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

Übungsblatt 1

Übungsblatt 2

Übungsblatt 3

Übungsblatt 4

Übungsblatt 5

Übungsblatt 6

Literatur

Beweis für den Satz von Kuratowskis
[Mak97] Yury Makarychev, A Short Proof of Kuratowski's Graph Planarity Criterion, 1997.
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.