Upward planarization and layout [Elektronische Ressource] / Hoi-Ming Wong

Sujets

• Informatik

Informations

• Publié par: technischen_universitat_dortmund
• Publié le: 01 janvier 2011
• Nombre de lectures: 96
• Langue: English
• Poids de l'ouvrage: 5 Mo

Extrait

Upward Planarization and Layout
Dissertation
zur Erlangung des Grades eines
Doktors der Naturwissenschaften
der Technischen Universit¨at Dortmund
an der Fakult¨at fur¨ Informatik
von
Hoi-Ming Wong
Dortmund
2011Tag der mundlic¨ hen Prufung:¨
26.09.2011
Dekanin:
Prof. Dr. Gabriele Kern-Isberner
Gutachter:
Prof. Dr. Petra Mutzel, Technische Universit¨ at Dortmund Dr. Christoph Buchheim, Technische Universit¨ at DortmundAbstract
Drawing directed graphs has many applications and occurs whenever a nat-
ural flow of information is to be visualized. Given a directed acyclic graph
(DAG)G, we are interested in an upward drawing ofG, that is, a drawing of
G in which all arcs are drawn as curves that are monotonically increasing in
the vertical direction. Besides the upward property, it is desirable that the
number of arc crossings arising in the drawing should be minimized.
In this thesis, we propose a new approach for drawing DAGs based on the
idea of upward planarization. We first introduce a novel upward planarization
approach for upward crossing minimization of DAGs that utilizes new ideas
for subgraph computation and arc reinsertion. In particular, it is the first
upward crossing minimization algorithm which does not utilize any layering
techniques known from the framework by Sugiyama et al. [STT81] or from
the upward planarization algorithm by Eiglsperger et al. [EKE03].
Our approach addresses the main weakness of the classical two step up-
ward crossing minimization approaches, where in the first step a layering of
the input DAG is computed and then, in the second step, the number of
crossings is minimized by solving the so-called k-level crossing minimization
problem (k-LCM). However, choosing an inappropriate layering in the first
step can negatively effect the subsequent k-level crossing minimization step,
thus causing many unnecessary arc crossings.
As shown by experimental evaluations, our new approach—referred to as
layer-free upward crossing minimization (LFUP)—outperforms the state-of-
the-art crossing minimization heuristics based on layering even if an exact
algorithm fork-level crossing is used. Furthermore, LFUP also
outperforms the existing approaches following the idea of upward planariza-
tion, that is, the approaches by Di Battista et al. [BPTT89] and Eiglsperger
et al. [EKE03].
We also present two extensions for the new approach: an extension for
upward planarization of directed hypergraphs and an extension for handling
given port constraints, that is, drawing constraints that arise due to the
prescribed positions where arcs can be connected to the drawing of the nodes.
The upward planarization approach LFUP computes an upward planar
representation (UPR)R of the input graph G, where crossings are modeled
by dummy nodes. We introduce a new layout approach for realizing UPRs,
that is, a drawing algorithm for constructing upward drawings where the arc
crossings arising in the drawing are the ones modeled by the dummy nodes in
R. Only few algorithms exist for realizing UPRs, most of these algorithms are
based on simple ideas and originally developed for drawing planar st-graphs,
hence our layout approach constitutes the first approach specialized for real-
izing UPRs. It offers two main advantages over the popular Sugiyama frame-
work: It benefits from the advantage of the upward planarization approach
LFUP, thus producing upward drawings with significantly less arc crossings.
iTherefore, the drawing quality increases considerably. Furthermore, while the
upward drawings produced by layer-based drawing approaches are often un-
structured and appear unnaturally flat, the new layout approach constructs
upward drawings that better reflect the structure of the digraphs and give a
tidier impression to the viewer.
iiZusammenfassung
Die Visualisierung von gerichteten azyklischen Graphen (DAGs) geh¨ ort zu
den wichtigsten Aufgaben im automatischen Zeichnen von Graphen. Hierbei
suchen wir fur¨ einen gegebenen DAG G eine Zeichnung von G (Aufw¨ arts-
zeichnung von G genannt), sodass alle Kanten als Kurven streng monoton
in vertikaler Richtung steigend gezeichnet werden. Um die Lesbarkeit der
Zeichnung zu erh¨ ohen, sollte neben der Aufw¨ artseigenschaft auch die Anzahl
der Kantenkreuzungen in der Zeichnung m¨ oglichst gering sein.
In dieser Dissertation entwerfen wir einen neuen Ansatz zur Visualisierung
von gerichteten Graphen, der auf der Idee der Aufw¨ artsplanarisierung basiert.
Wir stellen zuerst ein innovatives Aufw¨ artsplanarisierungverfahren vor, das
neue Techniken fur¨ die Berechnung aufw¨ artsplanare Untergraphen und die
anschließende Kanteneinfugephase¨ 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¨ artsplanarisierungsverfahren von Eiglsperger et al. [EKE03] kennen.
Die Festlegung einer Schichtung kann n¨ amlich zu sehr schlechten Ergebnissen
fuhren.¨ Folglich besitzt das neue Verfahren nicht die Nachteile der bisherigen
Kreuzungsminimierungsverfahren.
Experimentellen Analysen zeigen, dass das neue Aufw¨ artsplanarisierungs-
verfahren deutlich bessere Ergebnisse liefert als das klassische, auf Schich-
tungen basierende Kreuzungsminimierungsverfahren, und dies unabh¨ angig
von den benutzten L¨ osungsans¨ atzen (heuristisch oder optimal) fur¨ die k-
level Kreuzungsminimierungsphase. Auch im Vergleich mit den bekannten
Aufw¨ artsplanarisierungsverfahren (Di Battista et al. [BPTT89] und Eigls-
perger et al. [EKE03]) zeigt sich, dass der neue Ansatz weitaus bessere Ergeb-
nisse liefert. Wir stellen auch zwei Erweiterungen des neuen Ansatzes vor:
eine Erweiterung zur Aufw¨ artsplanarisierung von gerichteten Hypergraphen
und eine zur Unterstutzung¨ von Port Constraints.
Das Ergebnis der Aufw¨ ist eine aufw¨ artsplanare Re-
pr¨ asentation (UPR) — ein eingebetteter DAG, in dem Kreuzungen durch
kunstlic¨ he Dummy-Knoten modelliert werden. Wir stellen ein Layoutver-
fahren zur Realisierung solcher UPRs vor, d.h., ein Verfahren, das aus einem
UPR eine Aufw¨ artszeichnung 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 ursprunglic¨ h 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 gegenub¨ er dem etablierten Standardzeichenal-
gorithmus von Sugiyama et al.: Die Zeichnungen besitzen wesentlich weniger
Kreuzungen, was zur deutlichen Verbesserung der Lesbarkeit fuhrt.¨ Ferner
sind sie strukturierter und machen einen aufger¨ aumteren Eindruck.
iiiiv
Acknowledgment
Many people supported me during the time of research. Without their help,
this thesis would never have been possible. I wish to express here my gratitude
to all of them.
First of all, I want to thank my advisor Prof. Dr. Petra Mutzel who gave
me the opportunity to work with her and her research group at TU Dortmund.
I am grateful to my co-authors Carsten Gutwenger and Markus Chimani for
giving valuable advices regarding upward planarization and layouts and for
sharing their experience and knowledge. I also want to thank Miro Sp¨ onne-
mann for the fruitful cooperation and for sharing his knowledge about port
constraints and orthogonal drawings. Many thanks go to Nils Kriege and
Bernd Zey for proofreading parts of this thesis and Gundel Jankord for doing
all the administrative work. I am very grateful to Karsten Klein, the brave
fighter against “Kraut und Rub¨ en”, who gave me many helpful advices and
who sacrificed a lot of free time for proofreading this thesis. I want to thank
the members of my defense commission: Prof. Dr. Christoph Buchheim,
Prof. Dr. Ernst-Erich Doberkat, Prof. Dr. Petra Mutzel, and Dr. Moritz
Martens. Finally, I wish to thank my family and friends for their support.
Hoi-Ming Wong
Dortmund, 20116
v
Variable Description
a arc
a˜ arc to be reinserted
e arc/edge
f face
G graph
H hypergraph
L layering
R upward planar representation
s source
sˆ super source
t sink
ˆt super sink
U subgraph
u,v nodes
α hyperarc
γ combinatorial embedding
Γ (upward) planar embedding
line segment
Θ weight function
τ sink-switch
Notation Description
D drawing
u v a path from u to v
u v no path exists from u to v
|V| cardinality of set V
X(u) x-coordinate of node u
Y (u) y-co of node u
u≺v Y (u)< Y (y)
Abbreviation Description
BFS breadth-first search
DAG directed acyclic graph
DFS depth-first search
FUPS feasible upward planar subgraph
ILP integer linear programming
k-LCM k-level (multi-level) crossing minimization
LFUP layer-free upward planarization
SDP semidefinite programming
sT -graph single source DAG
UPL upward planarization layout
UPR upward planar representation
UIP u