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

Graph Drawing: Algorithms
for the Visualization of Graphs [von Roberto Tamassia, Giuseppe Di
Battista (Herausgeber), Ionnis G. Tollis] Animation

Proseminar: Graph Drawing

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



Zusammenfassung

Das Visualisieren struktureller Information ist für das Verständnis komplexer Zusammenhänge von entscheidender Bedeutung. Beispiele in der Informatik sind das Visualisieren von Datenbankmodellen in CASE-Tools, eine graphische Darstellung der Zustandsübergänge bei Automaten oder das Data-Mining. 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

Zeichnungen mit versch. Kurventypen

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, dass 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, dass Symmetrien oder Cluster in einem Graphen sichtbar werden oder dass 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.

Level-Zeichnung eines Binärbaumes

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ässt. Für den Fall, dass; 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. Das Feder-Modell zum Zeichnen beliebiger Graphen
  6. Testen eines Graphen auf Planarität
  7. Ein einfacher Algorithmus für das Zeichnen planarer Graphen
  8. Planarisierung von Graphen
  9. Färben von Landkarten (planare Graphen)
  10. Zeichnen von SP-Graphen
  11. Minimierung von Kantenkreuzungen bei allgemeinen Graphen
  12. 3-D Zeichnungen von Graphen
  13. Graph Drawing in Action: Anwendungen und Tools
  14. Spectral Drawing

Die Themenliste mit Literaturangaben als PostScript-Datei.


Ausarbeitungen

Die Liste der Ausarbeitungen findet sich auf folgender passwortgeschützten Web-Seite.


Termine und Betreuer

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

23.10.2001: Salah Qathifaci (erstes Treffen mit Betreuer spätestens am: 11.09.01)
Wie zeichnet man einen Graphen? (Thema 1)
Betreuer: Ulrich Rührmair
Harald Dobmeier (erstes Treffen mit Betreuer spätestens am: 18.09.01)
Schöne Zeichnungen von Bäumen (Thema 2)
Betreuer: Jens Ernst
30.10.2001: Roland Lindtner (erstes Treffen mit Betreuer spätestens am: 25.09.01)
Zeichnungen von Binärbäumen mit optimaler Fläche (Thema 3)
Betreuer: Ingo Rohloff
06.11.2001: Marcus Stade (erstes Treffen mit Betreuer spätestens am: 02.10.01)
Hierarchische Zeichnungen (Thema 4)
Betreuerin: Stefanie Gerke
13.11.2001: Andreas Volz (erstes Treffen mit Betreuer spätestens am: 09.10.01)
Das Feder-Modell zum Zeichnen beliebiger Graphen (Thema 5)
Betreuer: Hanjo Täubig
20.11.2001: Johannes Winkler (erstes Treffen mit Betreuer spätestens am: 16.10.01)
Testen eines Graphen auf Planarität (Thema 6)
Betreuerin: Stefanie Gerke
27.11.2001: Matthias Thar (erstes Treffen mit Betreuer spätestens am: 23.10.01)
Ein einfacher Algorithmus für das Zeichnen planarer Graphen (Thema 7)
Betreuer: Thomas Bayer
04.12.2001: Darina Velcheva (erstes Treffen mit Betreuer spätestens am: 30.10.01)
Planarisierung von Graphen (Thema 8)
Betreuer: Ingo Rohloff
11.12.2001: Cristina Opran (erstes Treffen mit Betreuer spätestens am: 06.11.01)
Färben von Landkarten (planare Graphen) (Thema 9)
Betreuer: Michal Mnuk
18.12.2001: Zlatina Savova (erstes Treffen mit Betreuer spätestens am: 13.11.01)
Zeichnen von SP-Graphen (Thema 10)
Betreuer: Thomas Schickinger
08.01.2001: Matthias Wimmer (erstes Treffen mit Betreuer spätestens am: 20.11.01)
Minimierung von Kantenkreuzungen bei allgemeinen Graphen (Thema 11)
Betreuer: Peter Ullrich
15.01.2001: Janos Kovats (erstes Treffen mit Betreuer spätestens am: 27.11.01)
Dreidimensionale Zeichnungen von Graphen (Thema 12)
Betreuer: Jens Ernst
22.01.2001: Karin Hostalka (erstes Treffen mit Betreuer spätestens am: 04.12.01)
Graph Drawing in Action: Anwendungen und Tools (Thema 13)
Betreuer: Peter Ullrich
29.01.2001: Matthias Bermuth (erstes Treffen mit Betreuer spätestens am: 11.12.01)
Spectral Drawing (Thema 14)
Betreuer: Klaus Holzapfel


Ablauf der Vorbereitung:

* Der Vortrag und die Ausarbeitung müssen mit dem Betreuer abgesprochen werden. Hierzu sind nachfolgende Terminvorgaben bindend (soweit nicht anders mit dem Betreuer abgestimmt). Werden die Termine nicht eingehalten, führt dies zur Streichung des Vortrags und zum Nichtbestehens des Seminars.
bis 5 Wochen vor dem Vortragerstes Treffen mit dem Betreuer (vor dem Treffen ist die Literatur bereits zu lesen); der genaue Termin ist bei den Vortragsterminen angegeben (durch die Weihnachtsferien verschiebt sich bei einigen der Termin nach vorne);
bis 3 Wochen vor dem VortragGliederung des Vortrags und der Ausarbeitung mit dem Betreuer besprechen;
bis 1 Woche vor dem Vortragfertige Folien und vollständige erste Version der Ausarbeitung mit dem Betreuer abstimmen;
bis 1 Woche nach dem Vortragfertige Ausarbeitung abgeben.

Anfertigung der Ausarbeitung

* Alle fertigen Ausarbeitungen werden nach dem Seminar gedruckt und an alle Teilnehmer verteilt. Damit eine einheitliche Form erzielt wird, müssen alle Ausarbeitungen mit dem Textsatzsystem LaTeX erstellte werden. Hierzu sind folgende Konventionen zu beachten:
  • Der folgende Rahmen ist zu verwenden (ausarbeitung.tex). Dabei dürfen die Seitengröße und der Font nicht verändert werden.
  • Ein Beispiel kann in der Datei example.tex gefunden werden (das Bild example.eps wird eingebunden)
  • Die Ausarbeitung soll auf die verwendete Literatur verweisen, diese Literatur ist mit BibTeX zu verwalten und in einer eigenen Datei zu speichern (hier die zum Beispiel gehörende Datei: example.bib).
* Bei Fragen zu LaTeX sei einerseits auf die folgenden Links hingewiesen, ferner kann auch der Betreuer um Hilfestellungen bzw. Literaturangaben gebeten werden.
* Eine weitere Anleitung zur Erstellung von Ausarbeitungen finden sie hier.

Hinweise zur Gestaltung der Vorträge

* Merkblatt zur Gestaltung eines Seminarvortrags. (Die Tipps auf diesem Merkblatt sind keine offiziellen Anforderungen oder Bewertungskriterien der TU München, sondern aus der Praxis eines Seminarleiters heraus entstandene Ratschläge.)
* Wer seine Folien mit LaTeX erstellen möchte findet hier einige Hinweise (einschließlich Rahmen-Datei als Vorlage)


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.
* Buch: Reinhard Diestel, Graphentheorie, 2. Auflage, Springer, 2000. ( Webseite mit elektronischer Ausgabe )
* Der Graph Drawing Server erlaubt es, einen Graphen interaktiv zu zeichnen und eine hübsches Layout berechnen und anzeigen zu lassen.

Konferenz Graph Drawing 2001 (Wien) 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: Klaus Holzapfel


Klaus Holzapfel Last modified: 10:13:23 Thu Feb 28 2002