|
WS 06/07 |
|||
Lehrstuhl Theoretische Informatik |
||||
Henning Fernau; Daniel Raible |
||||
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).
Einführung: Wie zeichnet man einen Graphen? Grundlage hierzu: Kapitel 1 und 2 aus GD sowie Kapitel 1 aus DG
Zeichnen von Wurzelbäumen: Kapitel 3.1 aus GD
Zeichnen von gerichteten seriell-parallelen Graphen: Kapitel 3.2 aus GD; ergänzend 3.2 aus DG
Testen eines Graphen auf Planarität: Kapitel 3.3 aus GD und Kapitel 2.3 aus DG
Planare Orientierungen I: Kapitel 4 bis einschließlich 4.5 aus GD
Planare Orientierungen II: Kapitel 4 von 4.6 bis einschließlich 4.7 aus GD
Inkrementelle Konstruktionen im Graphenzeichnen: Kapitel 7 aus GD
Hierarchische Zeichnungen: Kapitel 9 aus GD
Physikalische Modelle zum Zeichnen beliebiger Graphen: Kapitel 10 aus GD und Kapitel 4 aus DG
Zum Nachweis unterer Schranken: Kapitel 11 aus GD
(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)
Hierarchische Zeichnungen: Kapitel 5 aus DG zum Einstieg
Dreidimensionales Graphenzeichnen: Kapitel 7 aus DG zum Einstieg
Dynamisches Graphenzeichnen: Kapitel 9 aus DG zum Einstieg
Beschriften von Graphen: Kapitel 10 aus DG zum Einstieg
Approximationsalgorithmen im Graphenzeichnen: Nagamochis Arbeit von der GD 2003 als Einstieg
Exakte Algorithmen im Graphenzeichnen: Sudermans Dissertation gibt guten Überblick (hier auch 2 Vorträge möglich)
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%.
|
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; |
||||
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. |
||||
|
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: |
|
|
|
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.
|
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 ) |
|