Institut für Theoretische Informatik, Algorithmik
Suche
Institut für Theoretische Informatik, Algorithmik
Institut für Theoretische Informatik, Algorithmik
Institut für Theoretische Informatik, Algorithmik
Lehre
Sommersemester 2023
Algorithmen für planare Graphen

Algorithmen für planare Graphen

Sommersemester 2023

Allgemeines

Thema

Ein planarer Graph ist ein Graph, der in der Ebene gezeichnet werden kann, 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.

Vorlesungs-/Übungstermine

Dienstags und donnerstags 14:00 - 15:30.

Änderungen vorbehalten!

Dienstag Donnerstag
18.04. 1. Vorlesung 20.04. –
25.04. 2. Vorlesung 27.04. 3. Vorlesung
02.05. 1. Übung 04.05. 4. Vorlesung
09.05. 5. Vorlesung 11.05. 6. Vorlesung
16.05. 2. Übung 18.05. Feiertag
23.05. 7. Vorlesung 25.05. 8. Vorlesung
30.05. Pfingsten 01.06. Pfingsten
06.06. 3. Übung 08.06. Feiertag
13.06. 9. Vorlesung 15.06. 10. Vorlesung
20.06. 4. Übung 22.06. 11. Vorlesung
27.06. 12. Vorlesung 29.06. 5. Übung
04.07. 13. Vorlesung 06.07. 14. Vorlesung
11.07. 6. Übung 13.07.
18.07. 7. Übung 21.07. –
26.07. – 28.07. –

Übungen

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

Prüfungen

Es wird mündliche Prüfungen zu folgenden Terminen geben:

  • Donnerstag, 27.7.
  • Freitag, 28.7. (ausgebucht)
  • Dienstag, 1.8. (ausgebucht)
  • Dienstag, 8.8. (ausgebucht)
  • Dienstag, 29.8. (ausgebucht)
  • Mittwoch 30.8. (ausgebucht)
  • Donnerstag, 28.9. (ausgebucht)
  • Freitag, 29.9.
  • Donnerstag, 5.10. (ausgebucht)
  • Freitag, 6.10.
  • Montag, 16.10. (ausgebucht)
  • Dienstag, 17.10. (ausgebucht)

Anmeldung: Die Anmeldung erfolgt per e-Mail mindestens drei Wochen vorher an das Sekretariat sekr [dash] wagner [at] iti [dot] kit [dot] edu nach dem „first come, first served“-Prinzip. Bitte die Matrikelnummer angeben. Wir bemühen uns, passende Termine zuzuweisen, aber es gibt keine Garantie auf den Wunschtermin. Melden Sie sich also frühzeitig an (bis Ende der Vorlesungszeit).

Folien und Skripte

  • Das Skript zur Vorlesung im Sommersemester 2009
  • Skript zur Vorlesung Algorithmentechnik
  • Kurzskripte zur Wiederholung wichtiger Begriffe: Skriptsammlung
  • Ein Aufschrieb von Nils Froleyks zum Satz von Kuratowski. Dieser Aufschrieb ist ohne Gewähr auf Korrektheit.

Achtung: Es werden auch eine Reihe neuer Themen behandelt, die das Skript nicht abdeckt.

Literatur

Beweis für den Satz von Kuratowski
[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
[BK09] Glencora Borradaile and Philip Klein. An O(n log n) algorithm for maximum st-flow in a directed planar graph. J. ACM 56, 2, Article 9 (April 2009). (Erster O(n log n)-Algorithmus, auf dem der in der Vorlesung vorgestellt von Erickson [E10] aufbaut)
[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.
[ST81] Daniel D. Sleator and Robert Endre Tarjan. 1981. A data structure for dynamic trees. In Proceedings of the thirteenth annual ACM symposium on Theory of computing (STOC '81). Association for Computing Machinery, New York, NY, USA, 114–122. (Datenstruktur, die in [E10] verwendet wird)
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.