Universität Bonn

Institut für Informatik V

Prof. Dr. N. Blum, M. Nikolaidou, C. Rick

Seminar Planare Graphen: Theorie und Algorithmen
(WS 1999/2000)

Inhalt:

Viele graphentheoretische Probleme lassen sich auf planaren Graphen besser lösen. Das Seminar soll klären, warum dies der Fall ist. Dazu werden zunächst einige grundlegende kombinatorische Eigenschaften planarer Graphen besprochen. Daran schließt sich die Frage an, wie man testet, ob ein gegebener Graph planar ist. Ist der Graph planar, möchte man ihn natürlich gerne so aufzeichnen, daß sich keine Kanten überschneiden. Wie macht man das? Ist der Graph nicht planar, so stellt sich die Frage nach einem größten planaren Teilgraphen. Danach soll für eine Reihe von Problemen diskutiert werden, wie sie auf planaren Graphen effizienter oder (qualitativ) besser gelöst werden können, z.B. Färbung von Knoten und Kanten, Handlungsreisendenproblem, Finden von kantendisjunkten Pfaden etc.

Themenübersicht:

  1. Graphentheoretische Grundlagen (Euler, Kuratowski), 26.10.1999
  2. Graphentheoretische Grundlagen (Dualität), 2.11.1999
  3. Planaritätstest (Vertex-Addition), 9.11.1999
  4. Zeichnen Planarer Graphen (konvex), 16.11.1999
  5. Zeichnen Planarer Graphen (Gitter), 23.11.1999
  6. Knotenfärbung, 30.11.1999
  7. Unabhängige Knotenmengen, 7.12.1999
  8. Isomorphismustest, 14.12.1999
  9. Aufzählen von Teilgraphen, 11.1.2000
  10. Planare Seperatoren, 18.1.2000
  11. Maximale Schnitte, 25.1.2000
  12. Kantendisjunkte (s,t)-Pfade, 1.2.2000
Alle Kurzbeschreibungen als zip-Datei.

Seminartermin:

jeweils Dientags, 16-18 Uhr, N102

Bereich:

A/C

Vorbesprechung:

Dienstag, 29. Juni 1999, 16 c.t., N102

Voraussetzungen:

Vordiplomkenntnisse im Bereich Algorithmen und Datenstrukturen (insbesondere Graphenalgorithmen)

Vortragsmodus:

Vortragsausarbeitung, Einzelvortrag

Plätze:

14

Literatur:

Buchkapitel und Zeitschriftenartikel

Tips zur Vorbereitung eines Seminarvortrags:

  1. Regeln speziell für unser Seminar
  2. Student Speakers Guide

Universität Bonn / Informatik / Abteilung V

15.07.99 - rick@informatik.uni-bonn.de