Institut für Theoretische Informatik, Algorithmik

Seminar: Algorithmen für planare Graphen

Allgemeines

Aktuelles

  • 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

Vortragstermine

Freitag, 30. Januar, ab 11:30 im SR 301

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

Montag, 2. Februar, ab 16:00 im SR 236

  • Peter Mlynczak, Greedy Drawings of Triangulations

Mittwoch, 11. Februar, ab 9:00 im SR 236

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

Inhalt

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.

Voraussetzungen

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.

Voraussichtliche Themen

  • 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

Materialien