WS 07/08

Lehrstuhl Theoretische Informatik

Henning Fernau; Daniel Raible

Graph Drawing: Algorithmsfor the Visualization of Graphs [von Roberto Tamassia, Giuseppe DiBattista (Herausgeber), Ionnis G. Tollis] Animation

(Pro-)Seminar: Graphenzeichnen

[Zusammenfassung] [Themenliste] [Termine] [Hinweise]



Überblick

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.

Zeichnungen mit versch. Kurventypen2 ästhetische KriterienEine 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ärbaumesIn diesem (Pro-)Seminar sollen in den einzelnen Vorträgen grundlegende Ergebnisse aus diesem aktiven Forschungsgebiet vorgestellt werden. Im Proseminarteil werden wir uns vornehmlich mit Abschnitten aus dem Lehrbuch „Graph Drawing“ (GD), verfasst von Di Battista, Eades, Tamassia und Tollis, sowie einzelnen Abschnitten aus dem Tutorial „Drawing Graphs“ (DG), herausgegeben als LNCS 2025 von Kaufmann und Wagner, beschäftigen, während im Seminarteil Originalarbeiten zu dem Thema besprochen werden, meistens aufbauend auf einem ausgewählten Kapitel von DG. Die beiden genannten Bücher hat übrigens Herr Raible gerade ausgeliehen; sie können aber jederzeit (zumindest nach Absprache) von Interessierten eingesehen werden (Raum H 413).


Die folgenden Themen können im Proseminarteil bearbeitet werden:

  1. Einführung: Wie zeichnet man einen Graphen? Grundlage hierzu: Kapitel 1 und 2 aus GD sowie Kapitel 1 aus DG

  2. Zeichnen von Wurzelbäumen: Kapitel 3.1 aus GD

  3. Zeichnen von gerichteten seriell-parallelen Graphen: Kapitel 3.2 aus GD; ergänzend 3.2 aus DG

  4. Testen eines Graphen auf Planarität: Kapitel 3.3 aus GD und Kapitel 2.3 aus DG

  5. Planare Orientierungen I: Kapitel 4 bis einschließlich 4.5 aus GD

  6. Planare Orientierungen II: Kapitel 4 von 4.6 bis einschließlich 4.7 aus GD

  7. Inkrementelle Konstruktionen im Graphenzeichnen: Kapitel 7 aus GD

  8. Hierarchische Zeichnungen: Kapitel 9 aus GD

  9. Physikalische Modelle zum Zeichnen beliebiger Graphen: Kapitel 10 aus GD und Kapitel 4 aus DG

  10. Zum Nachweis unterer Schranken: Kapitel 11 aus GD


Die folgenden Themen können im Seminarteil bearbeitet werden:

(wir erwarten von den Seminarteilnehmern, dass sie sich nach Durcharbeiten der angegebenen Kapitel selbständig in einen sie besonders interessierenden Aspekt vertiefen und entsprechende Literatur in Absprache mit dem Betreuer studieren und für den Vortrag aufbereiten)

  1. Hierarchische Zeichnungen: Kapitel 5 aus DG zum Einstieg

  2. Dreidimensionales Graphenzeichnen: Kapitel 7 aus DG zum Einstieg

  3. Dynamisches Graphenzeichnen: Kapitel 9 aus DG zum Einstieg

  4. Beschriften von Graphen: Kapitel 10 aus DG zum Einstieg

  5. Approximationsalgorithmen im Graphenzeichnen: Nagamochis Arbeit von der GD 2003 als Einstieg

  6. Exakte Algorithmen im Graphenzeichnen: Sudermans Dissertation gibt guten Überblick (hier auch 2 Vorträge möglich)

  7. Formalsprachliche Methoden der Graphdarstellung

  8. Komplexitätstheoretische Probleme im Graphenzeichnen

Termine

Das (Pro-)Seminar wird in Blockform abgehalten, und zwar etwa einen Monat vor Ende dieses Semesters.

Genaueres wird noch auf dieser Seite bekanntgegeben.

Anmelden können sich Interessierte durch eine Email an Henning Fernau (fernau AT...) oder Daniel Raible (raible AT ...); zu ergänzen ist immer: informatik.uni-trier.de. Es wird allerdings dringend empfohlen, an der allgemeinen Vorbesprechung des (Pro-)Seminars teilzunehmen, die am Freitag, den 20.07.2007 um 13.45 Uhr im HS 13 stattfinden wird.

Scheinkriterien: Es gibt einen benoteten Schein.

Die Note setzt sich wie folgt zusammen: Vortrag 50%, Ausarbeitung 40%, aktive Teilnahme an Vortragsdiskussion 10%.

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 8 Wochen vor dem Vortrag

erstes Treffen mit dem Betreuer (vor dem Treffen ist die Literatur bereits zu lesen);

bis 4 Wochen vor dem Vortrag

Gliederung des Vortrags und der Ausarbeitung mit dem Betreuer besprechen; hierbei werden dem/r Vortragenden auch einige Testfragen zum Thema vorgelegt

bis 1 Woche vor dem Vortrag

fertige Folien und vollständige erste Version der Ausarbeitung mit dem Betreuer abstimmen;

bis 1 Woche nach dem Vortrag

fertige 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 erstellt werden. Hierzu sind folgende Konventionen zu beachten:

  • Es sollte 10-Punkt-Schrift in Standard-Latex eingestellt sein.

  • Die Ausarbeitung sollte nicht länger als 10 Seiten sein.

  • Bei der Einbindung von Bildern oder Graphiken ist darauf zu achten, dass sie lesbar ausgedruckt werden können.

  • Ein kleines Beispiel (von einem Mitarbeiter der TU München) sollte die Benutzung von LaTeX erläutern; Sie können dies gerne als Template für Ihre Ausarbeitung nehmen.

*

Bei Fragen zu LaTeX sei einerseits auf den folgenden Link hingewiesen, ferner kann auch der Betreuer um Hilfestellungen bzw. Literaturangaben gebeten werden.



Der Vortrag selbst sollte auf 50 Minuten angelegt sein. Abweichungen hiervon wirken sich auf die Note aus.


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 von Eppsein.

*

Buch: Reinhard Diestel, Graphentheorie, 2. Auflage, Springer, 2000. ( Webseite mit elektronischer Ausgabe )

*

Der Graph Drawing Server.