Algorithmen für planare Graphen

Sommersemester 2013

Allgemeines

  • Vorlesung: Dienstags, 14:00–15:30, SR 301 und Mittwochs, 14:00–15:30, SR 301 (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.

Prüfungstermine

Die Prüfungen für Bachelor in Informatik bzw. Mathematiker im Nebenfach finden geblockt direkt im Anschluß an die Vorlesungszeit und noch einmal kurz vor Beginn der nächsten Vorlesungszeit statt. Außerhalb dieser Zeiten ist eine Prüfung nur in Ausnahmefällen möglich.

Die Prüfungstermine in diesem Semester sind:

  • 7.8.2013
  • 21.8.2013
  • 8.10.2013

Anmeldungen im Sekretariat, Raum 319 bzw.per E-Mail bei lilian.beckert@kit.edu jeweils bis 10 Tage vor dem entsprechenden Prüfungstermin.

Die Prüfung findet im Raum 320 statt.

Prüfungstermine für die Vertiefungsfachprüfung im Diplom bitte per E-Mail bei den beteiligten Prüfern erfragen.

Neueste Meldungen

  • 2. Mai: Folien zum Planaritätstest sind online.
  • 8. Juli: Bei den weiterführenden Materialien findet sich nun ein kurzer Aufschrieb zu maximalen Flüssen in planaren Graphen.

Termine

Di Mi
16.04. Vorlesung 17.04. Vorlesung Folien zum Satz von Kuratowski
23.04. Übung
30.04. VorlesungFolien zu PQ-Bäumen und Planaritätstest
07.05. VorlesungFolien zur Färbung 08.05. Übung
14.05. Vorlesung
21.05. Vorlesung 22.05. Übung
28.05. Vorlesung
4.06. Vorlesung
11.06. Vorlesung (die Folien stehen leider nicht zur Verfügung :() 12.6. Übung
18.06. Vorlesung
25.06. Vorlesung
2.07. Vorlesung 3.07. Übung
9.07. Vorlesung
16.07. Vorlesung

Folien und Skripte

Achtung Dieses Jahr werden im Vergleich zu früheren Veranstaltungen eine Reihe neuer Themen behandelt. Das Skript eignet sich daher nicht als Ersatz für den Vorlesungsbesuch. Entsprechende Literatur wird in der Vorlesung bekannt gegeben.

Weiterführendes Material

Maximale Flüsse

Der vorgestellte Algorithmus basiert auf der Arbeit Maximum flows and parametric shortest paths in planar graphs, von Erickson, erschienen in Proceedings of Symposium on Discrete Algorithms, 2010, http://dl.acm.org/citation.cfm?id=1873601.1873666

Einen noch nicht ganz vollständigen Aufschrieb gibt es hier. Die fehlenden Teile werden nach und nach ergänzt, Feedback und konstruktive Kommentare sind herzlich willkommen.

Ü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

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
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.