Algorithmen für planare Graphen

• Dozent: Prof. Dr. Dorothea Wagner
• Ü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.

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.

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

• Das Skript zur Vorlesung im Sommersemester 2009
• Skript zur Vorlesung Algorithmentechnik
• Kurzskripte zur Wiederholung wichtiger Begriffe: Skriptsammlung

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.

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

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

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.