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 2011
Algorithmen für planare Graphen

Algorithmen für planare Graphen

Sommersemester 2011

Allgemeines

  • Dozenten: Prof. Dr. Dorothea Wagner
  • Vorlesung: in der Regel Dienstag um 13.10-14.40 Uhr im SR 301
  • Sondertermine:
    • Vorlesung Donnerstag, 5. Mai um 14:00-15:30 Uhr im SR 301 (stattdessen Dienstag, 3. Mai keine Vorlesung);
    • Vorlesung Donnerstag, 14. Juli um 14:00-15:30 Uhr im SR 301
  • Übungstermine:
    • Dienstag, 31. Mai um 13.10-14.40 Uhr im SR 301,
    • Donnerstag, 16. Juni um 14:00-15:30 im SR 301,
    • Dienstag, 5. Juli um 13.10-14.40 im SR 301
  • Informationen zur Vorlesung im offiziellen Vorlesungsverzeichnis

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

Prüfungstermine für Bachelor Informatik und Nebenfach Mathematik:

  • 19. Juli, um 8:30 -11:30 Uhr
  • 1. September, um 8:30 -12:30 Uhr
  • 13. September, um 8:30 -12:30 Uhr

Bis zum SS 2012, in dem diese Vorlesung wieder angeboten wird, biete ich einen weiteren Prüfungstermin an:

  • 30. November um 11.00 - 13.00 Uhr

Danach finden erst wieder im Anschuss an die Vorlesung im SS 2012 Prüfungen statt.

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

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

Neueste Meldungen

  • 31. März: Homepage zur Vorlesung ist online.
  • 33. April: Das zweite Übungsblatt ist online.
  • 24. Mai: Das dritte Übungsblatt ist online.
  • 24. Mai: Die Prüfungstermine für Bachelor Informatik und Nebenfach Mathematik sind online.
  • 31. Mai: Das vierte Übungsblatt ist online.
  • 20. Juni: Das fünfte Übungsblatt ist online.

Noch unvollständig, Änderungen vorbehalten!

Folien und Skripte

Übungen

Es wird alle 14 Tage ein Übungsblatt geben.

Vorlesungen

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.