Seminar über Graphenalgorithmen

S 19574 (SoSe2002)

SWS: 2S
Zeit: Dienstags 14-16
Ort: Takustraße 9, SR 053
Vorbesprechung: Dienstag 16.4., 14 Uhr c.t. (Eine erste Vorbesprechung hat bereits am Ende des Wintersemesters stattgefunden.)

Inhalt

In diesem Seminar werden einige Themen aus meiner Vorlesung über Graphenalgorithmen im
Wintersemester vertieft. Die Teilnehmerinnen halten auf der Grundlage von Spezialarbeiten einen Vortrag und fertigen eine kurze schriftliche Ausarbeitung an.

Themen

neue (andere?) Algorithmen zum Planaritätstest. (Eines dieser beiden Themen ist vergeben an A. Rakovski.)

Boyer & Myrvold
W. K. Shih and W. L. Hsu, A new planarity test, Theoretical Computer Science 223, (1999), 179-191. siehe auch Unterlagen dazu von Robin Thomas

Einbetten und Zeichnen von Graphen

in der Ebene: Kocay & Pantel, (Dieses Thema ist vergeben.)
in der Ebene: David Harel, Meir Sardas: An algorithm for straight-line drawing of planar graphs. Algorithmica 20 (1998), 119-135. (Dieses Thema ist vergeben.)
auf dem Torus, siehe auch "small graphs on the torus" (Dieses Thema ist vergeben an J. Wöss.)
in der projektiven Ebene (Myrvold und Roth) (Dieses Thema ist vergeben.)

symmetrisches Zeichnen von Graphen

Drawing graphs symmetrically in three dimensions (Seok-Hee Hong). (Dieses Thema ist vergeben an S. Schaust.)
W. Kocay and H. Carr, "An algorithm for drawing a graph symmetrically", Bulletin of the Institute of Combinatorics and its Applications 27 (1999), 19-25.

Zeichnen von Graphen auf dem Gitter mit möglichst wenigen Knicken

mit Hilfe von Flüssen:

Roberto Tamassia, On embedding a graph in the grid with the minimum number of bends. SIAM J. Computing 16 (1987), 421-444.

(Dieses Thema ist vergeben K. Holweger.)

Zerlegung in dreifache Zusammenhangskomponenten
dreifacher Zusammenhang mit PQ-Bäumen

Almira Karabeg: PQ-Trees and Triconnectivity, Ars Combinatoria 29A (1990), 13-31. (vergeben an S. Renkl.)
SPQR-Bäume (Dieses Thema ist wieder frei!)

Zerlegung von Graphen mit höherem Zusammenhang

Edmonds & Cunningham: A combinatorial decomposition theory. Canad. J. Math. 32 (1980) 734-765.

(Dieses Thema ist vergeben an R. Günzler.)

Konstruktion einer Kontraktionsfolge für dreifach zusammenhängende Graphen

siehe Diestel, Graphentheorie, Abschnitt 2.2, Satz 2.2.2

Voraussetzungen:

Vertrautheit mit den grundlegenden Begriffen aus der Graphentheorie (Bäume, Kreise, usw.) und mit elementaren Datenstrukturen zur Speicherung von Graphen im Computer. Algorithmisches Verständnis (Entwurf und Analyse von Algorithmen) ist hilfreich.

Perspektiven:

Studien- oder Diplomarbeiten können im Anschluss vergeben werden.

G. Rote, 22. 4. 2002