(Pro-)Seminar: Graphenzeichnen: WS 06/07

[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.

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.

In 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)

11. Hierarchische Zeichnungen: Kapitel 5 aus DG zum Einstieg

12. Dreidimensionales Graphenzeichnen: Kapitel 7 aus DG zum Einstieg

13. Dynamisches Graphenzeichnen: Kapitel 9 aus DG zum Einstieg

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

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

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

Termine

Das (Pro-)Seminar wird in Blockform abgehalten, und zwar in der allerletzten Vorlesungswoche 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 Donnerstag, den 26.10.2006 um 14 Uhr c.t. im HS 12 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:

Anfertigung der Ausarbeitung:

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

Interessante Links