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: Automatisiertes Zeichnen von Graphen

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

Zusammenfassung

Eine Zeichnung eines Graphen ist eine Darstellung dieser Beziehungen als Diagramm. Sie 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.

Graphenzeichnungen sollen vor allem zwei Anforderungen genügen: Sie sollen ``schön'' sein, aber auch die strukturellen Zusammenhänge der zugrundeliegenden Daten herausarbeiten. Es ist klar, daß manche Zeichnungen die enthaltene Information besser zum Ausdruck bringen als andere. Deshalb werden ästhetische Kriterien festgelegt, welche die Lesbarkeit von Graphen erhöhen sollen. Man kann etwa verlangen, daß Symmetrien oder Cluster in einem 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 automatisch liefern.

In diesem Proseminar sollen in den einzelnen Vorträgen 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. Für den Fall, daß letzteres nicht möglich ist, werden Algorithmen angewendet, die die Zahl der Kantenkreuzungen zumindest klein halten. Neben einigen weiteren Graphklassen und -algorithmen werden zudem aktuelle Anwendungen vorgestellt.

Die folgenden Themen werden bearbeitet:

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. Hierarchische Zeichnungen
5. Testen eines Graphen auf Planarität
6. Ein einfacher Algorithmus für das Zeichnen planarer Graphen
7. Planarisierung von Graphen
8. Minimierung von Kantenkreuzungen bei allgemeinen Graphen
9. Das Feder-Modell zum Zeichnen beliebiger Graphen
10. 3-D Zeichnungen von Graphen
11. Graph Drawing in Action: Anwendungen und Tools

Die Themenliste mit Literaturangaben als PostScript-Datei.

Das Proseminar findet voraussichtlich
dienstags von 14:00 (s.t.) Uhr bis 15: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.
	Der Graph Drawing Server erlaubt es, einen Graphen interaktiv zu zeichnen und eine hübsches Layout berechnen und anzeigen zu lassen.
	Drawing Graphs: Methods and Models, Michael Kaufmann und Dorothea Wagner (Eds.) (nur mit Zugangsberechtigung)

Konferenz Graph Drawing 2000 mit aktuellem Wettbewerb zum Graphenzeichnen

Jahreskonferenz zum Graphenzeichnen. Jedes Jahr werden Wettbewerbsgraphen vorgestellt, die schwierig zu zeichnen sind. Wer einen tollen Algorithmus hat und damit schöne Zeichnungen erstellen kann, sollte seine Lösungen einreichen.

Weitere Auskünfte bei: Mark Scharbrodt