Institut für Theoretische Informatik, Algorithmik

Algorithmen für planare Graphen

Sommersemester 2009

Allgemeines

  • Betreuer: Dr. Ignaz Rutter
  • Vorlesung: Wöchentlich dienstags 14.00-15.30 im SR 301 vom 21.04.2009 bis 21.07.2009
  • Übung: 14-täglich mittwochs 15.45-17.15 im SR 131, erstmals am 29.4.2009

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

  • 24. August: Im Skript wurden einige kleine Korrekturen vorgenommen.
  • 8. August: Die Materialien zu Planaritätstests sind online. Das benötigte Passwort erhalten Sie auf Anfrage per Email.
  • 14. Juli: Am 21. Juli hält Prof. Ulrik Brandes von der Universität Konstanz eine Vorlesung über lineare Planaritätstests. Die Vorlesung beginnt an diesem Tag erst um 14:30.
  • 15. Juni: Die Vorlesung vom Dienstag dem 16.6. ist verschoben auf den Übungstermin vom 17.6.
  • 9. Juni: Das überarbeitete Skript ist online.
  • 19. Mai: Achtung, die Übung am 27.05. findet im Allgemeinen Verfügungsgebäude (AVG) im SR -133 statt.
  • 2. März: Homepage zur Vorlesung ist online.

Termine

Di Mi
21.04. Vorlesung
28.04. Vorlesung 29.04. Übung
5.05. Vorlesung
12.05. Vorlesung 13.05. Übung
19.05. Vorlesung
26.05. Vorlesung 27.05. Übung
2.06. Vorlesung
9.06. Vorlesung 10.06. Übung
16.06. entfällt 17.06. Vorlesung
23.06. Vorlesung 24.06.
30.06. entfällt 01. 07 Übung
7.07. Vorlesung 8.07. Vorlesung
14.07 Vorlesung 15.07. Übung
21.07. Vorlesung 22.07. Übung

Änderungen vorbehalten!

Folien und Skripte

Die Materialien zu Planaritätstests sind Passwortgeschützt. Zugang erhalten Sie auf Anfrage bei Dr. Ignaz Rutter.

Übungen

Es wird alle 14 Tage ein Übungsblatt geben.

Ein Teil der Aufgaben soll schriftlich und in Zweiergruppen bearbeitet und abgegeben werden. Diese Aufgaben werden von uns korrigiert zurückgegeben. Die Lösungen der Aufgaben werden in der Übung vorgestellt. Zudem werden dort ausgewählte Themen der Vorlesung nochmals vertieft.

Vorlesungen

Datum Thema Material Literatur
21.04. Einführung, Grundlagen Skript, Kapitel 1,2 [Aig84] etc.
28.04. Satz von Kuratowski Skript, Kapitel 2 [Aig84]
5.05. Satz von Kuratowski, Dualgraphen Skript, Kapitel 2 [Aig84]
12.05. Färbung planarer Graphen, Planar Separator Theorem Skript, Kapitel 3, Kapitel 4 [Aig84], [RSST95], [T95],[T95b]
19.05. Planar Separator Theorem, Beweis Teil 2 Skript, Kapitel 4
26.05. Matchings Skript, Kapitel 5
2.06. Mixed Max Cut Skript, Kapitel 6
9.06. Mixed Max Cut, Teil 2; Via-Minimierung Skript, Kapitel 6
17.06. Menger-Problem Skript, Kapitel 7
23.06. Menger-Problem, Teil 2 Skript, Kapitel 7
7.07. Knotendisjunktes Menger-Problem Skript, Kapitel 7
8.07. Knotendisjunktes Menger-Problem, Okamura & Seymour, Teil 1 Skript, Kapitel 7, Kapitel 8
14.07. Okamura & Seymour, Teil 2 Skript, Kapitel 8

/

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