Algorithmen für planare Graphen
Allgemeines
- Dozentin: Prof. Dr. Dorothea Wagner
- Betreuer: Dipl.-Math. Steffen Mecke, Martin Holzer
- Vorlesung: Wöchentlich dienstags 11.30-13.00 im SR 301
vom 25.04.2006 bis 25.07.2006 - Übung: 14-täglich mittwochs 11.30-13.00 im SR 131, erstmals am 3.5.2006
- Mailingliste: Für wichtige Mitteilungen, Hinweise zu Übungsblättern und organisatorische Dinge bitten wir, sich auf der Mailingliste Planalgo einzutragen.
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
Termine
| Di | Mi | ||
|---|---|---|---|
| 25.04. | Vorlesung | ||
| 02.05. | Vorlesung | 03.05. | Übung |
| 9.05. | Vorlesung | ||
| 16.05. | Vorlesung | 17.05. | Übung |
| 23.05. | Vorlesung | ||
| 30.05. | Vorlesung | 31.05. | Übung |
| 06.06. | Vorlesung | ||
| 13.06. | Vorlesung | 14.06. | Übung |
| 20.06. | Vorlesung | ||
| 27.06. | Vorlesung | 28.06. | Übung |
| 04.07. | Vorlesung | ||
| 11.07. | Vorlesung | 12.07. | Übung |
| 18.07. | Vorlesung | ||
| 25.07. | Vorlesung | 26.07. | Übung |
Änderungen vorbehalten!
Folien und Skripte
- Vorläufige Version des neuen Skripts "Algorithmen auf planaren Graphen". Ein paar Details haben sich geändert und einige Fehler bis einschließlich Kapitel 6 sind korrigiert. Ansonsten ist das Layout stark verbessert worden.
- Skript zu einer früheren Instanz von "Algorithmen auf planaren Graphen", entspricht nicht dem Vorlesungsskript.
- Skript zur Vorlesung Algorithmentechnik
- Kurzskripte zur Wiederholung wichtiger Begriffe: Skriptsammlung
Übungen
Es wird alle 14 Tage ein Übungsblatt geben.
Vorlesungen
| Datum | Thema | Material | Literatur |
|---|---|---|---|
| 25.04. | Einführung, Grundlagen | Skript, Kapitel 1,2 | [Aig84] etc. |
| 02.05. | Satz von Kuratowski | Skript, Kapitel 2 | [Aig84] |
| 09.05. | Färbung planarer Graphen | Skript, Kapitel 3 | [Aig84], [RSST95], [T95],[T95b] |
| 16.05. | Planar Separator Theorem | Skript, Kapitel 4 | |
| 23.05. | Planar Separator Theorem, Beweis Teil 2 | Skript, Kapitel 4 | |
| 30.05. | Matchings | Skript, Kapitel 5 | |
| 06.06. | Mixed Max Cut | Skript, Kapitel 6 | |
| 13.06. | Mixed Max Cut, Teil 2; Via-Minimierung | Skript, Kapitel 6 | |
| 20.06. | Via-Minimierung, Teil 2 | Skript, Kapitel 6 | |
| 27.06. | Menger-Problem | Skript, Kapitel 7 | |
| 04.07. | Menger-Problem, Teil 2 | Skript, Kapitel 7 | |
| 11.07. | Okamura & Seymour | Skript, Kapitel 8 | |
| 18.07. | Okamura & Seymour, Teil 2 | Skript, Kapitel 8 | |
| 25.07. | Planaritätstests | [dBETT99, Kapitel 3.3], [BM04], [Tor] |
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. |