LEA
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]

Zeichnungen mit versch. Kurventypen

Zusammenfassung

Die Visualisierung struktureller Information ist von entscheidender Bedeutung für das Verständnis komplexer Zusammenhänge. Gerade im Bereich der Informatik tritt diese Aufgabe sehr häufig auf. Man denke beispielsweise an die graphische Darstellung eines Dateibaumes oder das Zeichnen des Flußdiagramms eines Algorithmus. Graphen sind ein ideales Hilfsmittel, um strukturelle Information abstrakt zu modellieren. Ein Graph besteht aus einer Menge von Knoten und einer Menge von Kanten. Eine Kante verläuft dabei zwischen zwei Knoten und beschreibt eine Beziehung zwischen diesen Knoten.

2 ästhetische Kriterien

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.

3 Darstellungen des 3-dim Hyperwürfels

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.

Level-Zeichnung eines Binärbaumes

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

24.6.97: Stefan Bischof
Einführung: Wie zeichnet man einen Graphen? (Thema 1)
1.7.97: Michael Winter
Schöne Zeichnungen von Bäumen (Thema 2)
Betreuerin: Ulla Koppenhagen
8.7.97: Michael Gnatz
Zeichnungen von Binärbäumen mit optimaler Fläche (Thema 3)
15.7.97: Martin Wagner
Testen eines Graphen auf Planarität (Thema 5)
Betreuer: Hans Stadtherr
15.7.97: Alexander Offtermatt
Planarisierung von Graphen (Thema 7)
Betreuer: Tom Friedetzky
22.7.97: Jörg Dolak
Das Feder-Modell zum Zeichnen beliebiger Graphen (Thema 8)
Betreuer: Ulrich Voll
29.7.97: Andreas Birnböck
Zeichnen dynamischer Bäume (Thema 10)
Betreuer: Volker Heun


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.


Stefan Bischof, 9.1.1998
Tobias Knopff, 1997-04-15