Fakultät für Informatik der Technischen Universität München Lehrstuhl für Effiziente Algorithmen Postadresse: 80290 München; Hausadresse: Arcisstr.21, 80333 München

Proseminar: Zeichnen von Graphen

Zeit: Di 15:00 (s.t.) - 16:30, Raum S2229

[Zusammenfassung] [Themenliste] [Termine] [Ausarbeitungen] [Links]

Zusammenfassung

Eine Zeichnung eines Graphen ordnet den Knoten Symbole (etwa Kreise oder Rechtecke) und Koordinaten (meist in der euklidischen Ebene) zu. Die Kanten werden durch Kurven zwischen den zugehörigen Knotensymbolen dargestellt.

Beispiele für erlaubte Kurven sind Polygonzüge, orthogonale Polygonzüge oder Geradensegmente. Es ist klar, daß manche Zeichnungen die enthaltene Information besser zum Ausdruck bringen als andere. Deshalb werden ästhetische Kriterien festgelegt, die Zeichnungen von Graphen lesbar machen sollen. Man kann etwa verlangen, daß Symmetrien eines Graphen sichtbar werden oder daß die Anzahl der Schnittpunkte von Kanten möglichst klein ist. Diese Kriterien sind jedoch subjektiv und kontextabhängig. Sind die Anforderungen an die Darstellung einer Klasse von Graphen einmal festgelegt, dann versucht man, effiziente Algorithmen zu entwickeln, die möglichst gute Zeichnungen liefern.

In diesem Proseminar sollen in den einzelnen Vorträgen einige grundlegende Ergebnisse aus diesem aktiven Forschungsgebiet vorgestellt werden. Es werden zuerst Algorithmen für das Zeichnen von Bäumen untersucht. Dann wird der Frage nachgegangen, wann sich ein Graph ohne Überschneidungen von Kanten zeichnen läßt. Neben einigen weiteren Graphklassen wird abschließend auf Algorithmen eingegangen, die in der Lage sind, sich dynamisch verändernde Graphen effizient zu zeichnen.

Die folgenden Themen stehen zur Auswahl:

1. Einführung: Wie zeichnet man einen Graphen?
2. Schöne Zeichnungen von Bäumen
3. Zeichnungen von Binärbäumen mit optimaler Fläche
4. Optimierung der Fläche und des Seitenverhältnisses orthogonaler Baumdarstellungen
5. Testen eines Graphen auf Planarität
6. Ein einfacher Algorithmus für das Zeichnen planarer Graphen
7. Planarisierung von Graphen
8. Das Feder-Modell zum Zeichnen beliebiger Graphen
9. Visualisierung serienparalleler Graphen
10. Zeichnen dynamischer Bäume
11. Zeichnungen dynamischer Graphen: ein allgemeines Modell

Die Themenliste mit Literaturangaben als PostScript-Datei.

Das Proseminar findet dienstags von 15:00 (s.t.) Uhr bis 16:30 Uhr im Raum S2229 statt.

Termine und Betreuer

Interessante Links

	Die Grundlagen für das Zeichen von Graphen von Isabel F. Cruz und Roberto Tamassia (farbige, gezippte PostScript-Datei, 80995 Bytes).
	Ein gute Übersicht über Algorithmen für das Zeichnen von Graphen von Roberto Tamassia (gezippte PostScript-Datei, 106454 Bytes).
	Jede Menge Hyperlinks über Theorie und Praxis des Graph-Drawing.
	Für Leute mit Geduld und guten Nerven: Der Graph Drawing Server, Version 1.0 (sicher nicht die letzte ;-) mit Java-Interface, erlaubt es einen Graphen interaktiv zu zeichnen und eine hübsches Layout berechnen und anzeigen zu lassen.

Weitere Auskünfte erteilt Stefan Bischof.