Institut für Theoretische Informatik, Algorithmik

Algorithmen für planare Graphen

Sommersemester 2015

Allgemeines

  • Übungsleiter: Dr. Thomas Bläsius
  • Vorlesung: Dienstags, 14:00–15:30, Hörsaal II - Gebäude 30.41 - Chemie Flachbau und Mittwochs, 14:00–15:30, Mittlerer Hörsaal - Gebäude 10.91 - Maschinenbau (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üfungstermine in diesem Semester sind:

  • 24. Juli
  • 30. Juli ausgebucht!
  • 4. September ausgebucht!
  • 11. September ausgebucht!
  • 5. Oktober ausgebucht!
  • 12. Oktober ausgebucht!

Wegen der großen Nachfrage gibt es den folgenden zusätzlichen Prüfungstermin:

  • 3. September

Anmeldung: Die Anmeldung erfolgt per e-Mail an Lilian Beckert nach dem „first come, first served“-Prinzip.

Wichtig: Die Anmeldung muss bis spätestens 3 Wochen vor dem Prüfungstermin erfolgen.

Termine

Vorlesungen bzw. Übungen verden voraussichtlich an den folgenden Terminen stattfinden.

Di Mi
14.04. Vorlesung 15.04. Vorlesung Folien zum Satz von Kuratowski
21.04. Vorlesung 22.04. Übung
28.04. - 29.04. Vorlesung Folien zur Färbung
05.05. Vorlesung Folien zu Separatoren 06.05. Übung
12.05. Vorlesung 13.05. -
19.05. Übung 20.05. Vorlesung
26.05. Vorlesung Folien zu Flüssen 27.05. Vorlesung
02.06. Übung 03.06. Vorlesung
09.06. Vorlesung 10.06. Übung Bilder zu Aufgabe 2
16.06. Vorlesung 17.06. Vorlesung
23.06. Übung 24.06. Gastvorlesung von Prof. Stephen Kobourov
30.06. Vorlesung Folien zum Planaritätstest 01.07. Übung
07.07. - 08.07. -

Folien und Skripte

Achtung: Es werden auch eine Reihe neuer Themen behandelt, die das Skript nicht abdeckt. Das Skript eignet sich daher nicht als Ersatz für den Vorlesungsbesuch. Entsprechende Literatur wird in der Vorlesung bekannt gegeben.

Übungen

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

Übungsblatt 1

Übungsblatt 2

Übungsblatt 3

Übungsblatt 4

Übungsblatt 5

Übungsblatt 6

Übungsblatt 7

Gastvortrag im Rahmen der Vorlesung

Am 24. Juni wird Prof. Stephen Kobourov einen Vortrag im Rahmen der Vorlesung halten. Der Titel des Vortrags lautet

Proportional Contact Representation of Planar Graphs

Abstract

In a proportional contact representation of a planar graph, each vertex is represented by a simple polygon with area proportional to a given weight, and edges are represented by adjacencies between the corresponding pairs of polygons. We show how to use Schnyder realizers and canonical orders for planar graphs to obtain different types of contact representations. Specifically, we describe an algorithm that guarantees 10-sided rectilinear polygons and runs in linear time. We also describe a construction with 8-sided polygons, which is optimal in terms of polygonal complexity as 8-sided polygons are sometimes necessary. Specifically, we show how to compute the combinatorial structure and how to refine it into an area-universal rectangular layout in linear time. However, to compute the exact representation from the area-universal layout required numerical iteration, or can be approximated with a hill-climbing heuristic.

Literatur

Beweis für den Satz von Kuratowskis
[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
[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.
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.