Upward planarization and layout
Creators: name: Wong, Hoi-Ming
Publisher: name: Technische Universität Dortmund
Year: 2011
Subjects: subject: Graph drawing
subject: Graph layout
subject: Hierarchical drawings
subject: Upward
subject: Upward planarization
subject: 004

description: 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.