Upward planarization and layout
Loading...
Date
2011-10-06
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Die Visualisierung von gerichteten azyklischen Graphen (DAGs) gehört zu
den wichtigsten Aufgaben im automatischen Zeichnen von Graphen. Hierbei
suchen wir für einen gegebenen DAG G eine Zeichnung von G (Aufwärtszeichnung
von G genannt), sodass alle Kanten als Kurven streng monoton
in vertikaler Richtung steigend gezeichnet werden. Um die Lesbarkeit der
Zeichnung zu erhöhen, sollte neben der Aufwärtseigenschaft auch die Anzahl
der Kantenkreuzungen in der Zeichnung möglichst gering sein.
In dieser Dissertation entwerfen wir einen neuen Ansatz zur Visualisierung
von gerichteten Graphen, der auf der Idee der Aufwärtsplanarisierung basiert.
Wir stellen zuerst ein innovatives Aufwärtsplanarisierungverfahren vor, das
neue Techniken für die Berechnung aufwärtsplanare Untergraphen und die
anschließende Kanteneinfügephase einsetzt. Vor allem werden in dem neuen
Verfahren keine Schichtungstechniken zur Kreuzungsminimierung benutzt,
wie wir sie aus dem Zeichenverfahren von Sugiyama et al. [STT81] oder aus
dem Aufwärtsplanarisierungsverfahren von Eiglsperger et al. [EKE03] kennen.
Die Festlegung einer Schichtung kann nämlich zu sehr schlechten Ergebnissen
führen. Folglich besitzt das neue Verfahren nicht die Nachteile der bisherigen
Kreuzungsminimierungsverfahren.
Experimentellen Analysen zeigen, dass das neue Aufwärtsplanarisierungsverfahren
deutlich bessere Ergebnisse liefert als das klassische, auf Schichtungen
basierende Kreuzungsminimierungsverfahren, und dies unabhängig
von den benutzten Lösungsansätzen (heuristisch oder optimal) für die klevel
Kreuzungsminimierungsphase. Auch im Vergleich mit den bekannten
Aufwärtsplanarisierungsverfahren (Di Battista et al. [BPTT89] und Eiglsperger
et al. [EKE03]) zeigt sich, dass der neue Ansatz weitaus bessere Ergebnisse
liefert. Wir stellen auch zwei Erweiterungen des neuen Ansatzes vor:
eine Erweiterung zur Aufwärtsplanarisierung von gerichteten Hypergraphen
und eine zur Unterstützung von Port Constraints.
Das Ergebnis der Aufwärtsplanarisierung ist eine aufwärtsplanare Repräsentation (UPR) — ein eingebetteter DAG, in dem Kreuzungen durch
künstliche Dummy-Knoten modelliert werden. Wir stellen ein Layoutverfahren
zur Realisierung solcher UPRs vor, d.h., ein Verfahren, das aus einem
UPR eine Aufwärtszeichnung konstruiert, sodass die Kantenkreuzungen in
der Zeichnung zu den Dummy-Knoten des gegebenen UPR korrespondieren.
Die wenigen existierenden Zeichenverfahren zur Realisierung von UPRs sind
sehr einfach und wurden ursprünglich entwickelt, um planare st-Graphen zu
zeichnen. Unser neues Verfahren stellt somit das erste Layoutverfahren dar,
das speziell im Hinblick auf die Realisierung von UPRs entworfen wurde. Es
bietet zwei wichtige Vorteile gegenüber dem etablierten Standardzeichenalgorithmus
von Sugiyama et al.: Die Zeichnungen besitzen wesentlich weniger
Kreuzungen, was zur deutlichen Verbesserung der Lesbarkeit führt. Ferner
sind sie strukturierter und machen einen aufgeräumteren Eindruck.
Description
Table of contents
Keywords
Graph drawing, Graph layout, Hierarchical drawings, Upward, Upward planarization