Seminar: Algorithmen für planare Graphen

• Betreuung: Dr. Reinhard Bauer, Dr. Marcus Krug, Dr. Ignaz Rutter, Prof. Dr. Dorothea Wagner
• Vorbesprechung: Freitag, 24. Oktober, 11:30 im SR 301, Informatikgebäude 50.34
• Teilnahme: Die Teilnehmerzahl ist auf zwölf Personen begrenzt.

• 2. März 2009: Vorlage für die Ausarbeitung verfügbar
• 24. Oktober 2008: Vorbesprechungsfolien verfügbar
• 9. September 2008: Themenliste und Materialien verfügbar

• Michael Ziller, Tremaux Trees and Planarity
• Adriante Runte Inserting an Edge into a Planar Graph

• Peter Mlynczak, Greedy Drawings of Triangulations

• Richard Stefanec, Subgraph Isomorphism in Planar Graphs and Related Problems
• Tobias Columbus, Fast 3-Coloring Triangle-Free Planar Graphs

Planare Graphen sind Graphen, die sich ohne Kreuzung in die Ebene zeichnen lassen. Die spezielle Struktur von planaren Graphen erlaubt es in vielen Fällen Probleme auf planaren Graphen deutlich effizienter zu lösen als im allgemeinen Fall. So lassen sich einige im allgemeinen Fall NP-schwere Probleme auf planaren Graphen effizient lösen, andere lassen sich zumindest deutlich besser (oder überhaupt) approximieren. Im Seminar sollen fortgeschrittene Techniken zum Lösen von Problemen auf planaren Graphen vorgestellt werdenen. Dazu stehen sowohl klassische Themen, als auch neuere Veröffentlichungen der letzten Jahre zur Auswahl.

Voraussetzung für die Teilnahme sind Kenntnisse aus Algorithmentechnik, insbesondere Graphentheorie und das O-Kalkül. Kenntnisse aus der Vorlesung Algorithmen für planare Graphen sind nützlich, werden aber nicht vorausgesetzt.

• Subgraph Isomorphism in Planar Graphs and Related Problems,
  David Eppstein, 1999
• Inserting an Edge into a Planar Graph,
  Carsten Gutwenger, Petra Mutzel, René Weiskircher, 2005
• An O(n log n) algorithm for maximum st-flow in a directed planar graph,
  Glencora Borradaile, Philip Klein, 2006
• Planarity Algorithms via PQ-Trees,
  Bernhard Haeupler, Robert E. Tarjan, 2008
• Depth-First Search and Planarity,
  Hubert de Fraysseix, Patrice Ossona de Mendez, Pierre Rosenstiehl, 2006
• Edge-Disjoint Paths in Planar Graphs,
  C. Chekuri, S. Khanna, F.B. Shepherd, 2004
• A Polynomial-Time Approximation Scheme for Steiner Tree in Planar Graphs,
  Glencora Borradaile, Claire Kenyon-Mathieu, Philip Klein
• Preprocessing an undirected planar network to enable fast approximate distance queries, Philip Klein
• Fast 3-Coloring Triangle-Free Planar Graphs,
  Lukasz Kowalik, 2004
• A linear-time approximation scheme for planar weighted TSP,
  Philip Klein, 2005
• Greedy drawings of triangulations,
  Raghavan Dhandapani, 2008

• Seite der Vorlesung Algorithmen für planare Graphen, insbesondere das Skript
• Skript zur Vorlesung Algorithmentechnik
• Kurzskripte zu Grundlagen
  • Algorithmen und ihre Laufzeit
  • Begriffe der Graphentheorie
  • Die Komplexitätsklassen P, NP und NPC