Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Orthogonal graph drawing with constraints [Elektronische Ressource] : algorithms and applications / vorgelegt von Martin Siebenhaller

222 pages
Orthogonal Graph Drawingwith Constraints:Algorithms and ApplicationsDissertationder Fakultat fur Informations- und Kognitionswissenschaften¨ ¨der Eberhard-Karls-Universita¨t Tu¨bingenzur Erlangung des Grades einesDoktors der Naturwissenschaften(Dr. rer. nat.)vorgelegt vonDipl.-Inform. Martin Siebenhalleraus MeersburgTu¨bingen2009Tag der mu¨ndlichen Qualifikation: 16.12.2009Dekan: Prof. Dr.-Ing. Oliver Kohlbacher1. Berichterstatter: Prof. Dr. Michael Kaufmann2. Berichterstatter: Prof. Dr. Wolfgang Ku¨chlinAcknowledgmentsWriting this thesis would not have been possible without the great supportof various people. First of all I want to thank my advisor Prof. Dr. MichaelKaufmann for all his support, for introducing me to the interesting field ofgraphdrawing,forgivingmetheopportunitytobepartofhisresearchgroupand for providing me the possibility to attend several international work-shops and conferences. I am also very grateful to Dr. Markus Eiglspergerfor guiding me through my first steps of designing and implementing graphdrawing algorithms. I would like to thank the Deutsche Forschungsgemein-schaft (DFG) for financial support of our research under grant Ka 812/8-3and the yWorks company for providing both the yFiles library and theirtechnical support. Further, I want to thank all my co-authors for the suc-cessful cooperation as well as the rest of the research group, namely PhilipEffinger, Andreas Gerasch, Markus Geyer, Stephan Kottler and Dr.
Voir plus Voir moins

Orthogonal Graph Drawing
with Constraints:
Algorithms and Applications
Dissertation
der Fakultat fur Informations- und Kognitionswissenschaften¨ ¨
der Eberhard-Karls-Universita¨t Tu¨bingen
zur Erlangung des Grades eines
Doktors der Naturwissenschaften
(Dr. rer. nat.)
vorgelegt von
Dipl.-Inform. Martin Siebenhaller
aus Meersburg
Tu¨bingen
2009Tag der mu¨ndlichen Qualifikation: 16.12.2009
Dekan: Prof. Dr.-Ing. Oliver Kohlbacher
1. Berichterstatter: Prof. Dr. Michael Kaufmann
2. Berichterstatter: Prof. Dr. Wolfgang Ku¨chlinAcknowledgments
Writing this thesis would not have been possible without the great support
of various people. First of all I want to thank my advisor Prof. Dr. Michael
Kaufmann for all his support, for introducing me to the interesting field of
graphdrawing,forgivingmetheopportunitytobepartofhisresearchgroup
and for providing me the possibility to attend several international work-
shops and conferences. I am also very grateful to Dr. Markus Eiglsperger
for guiding me through my first steps of designing and implementing graph
drawing algorithms. I would like to thank the Deutsche Forschungsgemein-
schaft (DFG) for financial support of our research under grant Ka 812/8-3
and the yWorks company for providing both the yFiles library and their
technical support. Further, I want to thank all my co-authors for the suc-
cessful cooperation as well as the rest of the research group, namely Philip
Effinger, Andreas Gerasch, Markus Geyer, Stephan Kottler and Dr. Katha-
rina Zweig, for providing a pleasant working environment and for relaxing
coffee breaks. Special thanks also to the proofreaders Marc B´egin, Philip
Effinger, Stephan Kottler and Thomas Wurst. Last but not least, I want to
thank my parents for supporting my studies.ivDeutsche Zusammenfassung
Die Visualisierung ist ein bew¨ahrtes und probates Mittel fu¨r die Repr¨asen-
tation von Daten. Aufgrund der kognitiven F¨ahigkeiten von Menschen er-
leichtert eine Visualisierung (graphische Darstellung) das Aufnehmen und
Verstehen der in den Daten enthaltenen Informationen. Die vorliegende
Arbeit besch¨aftigt sich mit der Graph-basierten Visualisierung, d. h. der
Visualisierung von Daten, die durch Graphen beschrieben werden k¨onnen.
EinGraphisteinKonstruktderMathematik(Graphentheorie)undwird
zurModellierungvonbin¨arenRelationenzwischenObjektenverwendet. Die
Objekte werden dabei h¨aufig als Knoten“ und die Relationen als Kan-
” ”
ten“ bezeichnet. Das Forschungsgebiet, welches sich mit der Visualisierung
vonGraphen, imSpeziellen mit demautomatischen Anordnen(Layout) von
Knoten und Kanten besch¨aftigt, heißt Graphenzeichnen“. Beim Zeichnen

von Graphen werden Knoten u¨blicherweise als Punkte/Rechtecke und Kan-
ten als Kurven repr¨asentiert. Außerdem werden verschiedene ¨asthetische
Anforderungen beru¨cksichtigt, z. B. soll die Anzahl der Kantenkreuzungen
in der resultierenden Zeichnung m¨oglichst gering sein.
In orthogonalen Zeichnungen von Graphen werden die Kanten durch
Polygonzu¨ge dargestellt, die aus abwechselnd horizontalen und vertikalen
Liniensegmenten bestehen. Das bekannteste Verfahren zur Erzeugung von
orthogonalen Zeichnungen ist der Topology-Shape-Metrics“ Ansatz (TSM-

Ansatz), der aus den Phasen Planarisierung, Orthogonalisierung und Kom-
paktierung besteht. Im Gegensatz zu den sogenannten kr¨aftebasierten und
hierarchischen Zeichenverfahren, wird der TSM-Ansatz in der Praxis nur
selteneingesetzt. Dasliegtzumeinenandessenh¨oheremImplementierungs-
aufwand, zum anderen daran, dass im Vergleich zu den beidenanderen Ver-
fahren nur wenige Erweiterungen zur Einbeziehung von Nebenbedingungen
bezu¨glich der Anordnung der Graphelemente bekannt sind.
DieFormulierungsolcherNebenbedingungenistnotwendig,umgeeignete
Visualisierungenfu¨rAnwendungenausBereichenwieSoftware-Technik,Bio-
informatik und Netzwerkanalyse zu erzeugen. In der vorliegenden Arbeit
wird ein neues Zeichenverfahren pr¨asentiert, welches auf dem TSM-Ansatz
basiert und die folgenden Nebenbedingungen unterstu¨tzt:vi
• Eine Teilmenge der Kanten wird durch monoton steigende Kurven
repr¨asentiert. Diese Kanten besitzen also eine einheitliche Flussrich-
tung.
• Eine Teilmenge der Knoten wird bimodal“ gezeichnet, d. h. so, dass

die eingehenden und ausgehenden Kanten eines Knotens, bezu¨glich
ihrer Reihenfolge um den Knoten, getrennt voneinander erscheinen.
• Zusammengeh¨origeKnotenwerdenzuClusterngruppiert. JederClus-
ter wird durch eine rechteckige Region repr¨asentiert, welche genau die
zum Cluster geh¨orenden Knoten beinhaltet. Die Position eines Clus-
ters wird dabei nicht vorgegeben.
• Die Zeichenfl¨ache wirdin Rechtecke zerlegt. Jeder Knoten wirdinner-
halb eines vorgegebenen Rechtecks platziert.
• Die m¨oglichen Anschlusspunkte einer Kante an einem dazugeh¨origen
Knoten werden durch die Vorgabe einer Seite oder einer genauen Po-
sition am Knotenrand eingeschr¨ankt.
Bislang ist kein TSM-basiertes Verfahren bekannt, dass eine solch kom-
plexeKombinationvonNebenbedingungenzul¨asst. Fu¨rdieEntwicklungder
entsprechenden Algorithmen wird auf bew¨ahrte Methoden und Konzepte
aus dem Bereich des Graphenzeichnens zuru¨ckgegriffen. Wie der Titel der
Arbeit bereits verr¨at, werden nicht nur neue Algorithmen pr¨asentiert, son-
dern diese auch im praktischen Einsatz getestet. Die erzielten Ergebnisse
best¨atigen, dass das Verfahren gut fu¨r die Visualisierung praktischer An-
wendungen geeignet ist.
Im Einzelnen gliedert sich die Arbeit wie folgt: Nach einer kurzen Ein-
fu¨hrung in die Thematik werden im zweiten Kapitel zun¨achst grundlegende
mathematischeKonzepteundDefinitionenausdemBereichderGraphenthe-
¨orie erl¨autert. Danach wird ein Uberblick u¨ber verschiedene Anforderungen
und Konventionen, die beim Zeichnen von Graphen von Bedeutung sind,
gegeben. Es werden die einzelnen Phasen des TSM-Ansatzes beschrieben
unddashierarchischeZeichenverfahrenvonSugiyama(Sugiyama-Verfahren)
vorgestellt.
Im dritten Kapitel werden die oben genannten Nebenbedingungen ana-
¨lysiert und ein Uberblick u¨ber bereits bestehende verwandte theoretische
und praktische Arbeiten gegeben. Nach der Vorstellung der verschiede-
nen Nebenbedingungen werden die Probleme, die durch deren gleichzeitige
¨Verwendung entstehen k¨onnen, betrachtet. Außerdem wird ein Uberblick
u¨berdie einzelnen Schritte des neuenZeichenverfahrens gegeben unddessen
Schnittstelle beschrieben.
Im vierten Kapitel wird das neue Planarisierungsverfahren eingefu¨hrt,
welches die fu¨nf Nebenbedingungen einbindet. Dabei wird auch eine beson-
derseffiziente ImplementierungdesSugiyama-Verfahrens vorgestellt, welchevii
den existierenden Implementierungen bezu¨glich der Laufzeit und des Spei-
cherverbrauchsweitu¨berlegenist. Dieentwickelte Planarisierungsphasever-
wendet diese Implementierung in einem Zwischenschritt.
In Kapitel fu¨nf wird ein Orthogonalisierungsverfahren vorgestellt, wel-
ches die Nebenbedingungen beru¨cksichtigt. Die Orthogonalisierung basiert
auf dem bekannten Kandinsky“-Verfahren und dessen Erweiterungen, wel-

che dasVorgeben von Kantenknicken undWinkeln zwischen Kanten erm¨og-
lichen. Eswirdaufgezeigt, wiedieverschiedenenNebenbedingungenmithilfe
dieser Erweiterungen realisiert werden k¨onnen.
ImsechstenKapitelwerdenalternativePlanarisierungs-undOrthogonal-
isierungsverfahren fu¨r die Modellierung von Nebenbedingungen, welche die
m¨oglichen Anschlusspunkte der Kanten an Knoten einschr¨anken, beschrie-
ben. Dabeiwirdaucheinorthogonales Zeichenverfahrenvorgestellt, welches
nicht auf dem TSM-Ansatz, sondern einer anderen Methode beruht.
Die Tauglichkeit der in dieser Arbeit vorgestellten Algorithmen und
Methoden wird im siebten Kapitel demonstriert. Zuerst wird das neue
Verfahren zum Zeichnen von UML-Aktivit¨atsdiagrammen eingesetzt. Dazu
¨werden die entsprechenden Anforderungen ermittelt, ein Uberblick u¨ber
bestehendeverwandte Arbeitengegeben unddieResultate derinbekannten
UML-Werkzeugen verwendeten Zeichenverfahren untersucht. Die Qualit¨at
des Verfahrens wird anhand verschiedener Beispieldiagramme belegt. Im
zweitenTeildesKapitelswirdeineVisualisierungsmethodefu¨rAusfu¨hrungs-
graphen von parallelen Programmabl¨aufen pr¨asentiert. Diese Methode ba-
siert auf der schnellen Implementierung des Sugiyama-Verfahrens. Wieder
werdendieentsprechendenAnforderungenermitteltundverwandteArbeiten
aufdiesemGebietvorgestellt. DieVisualisierungsmethodewirdmittelseiner
repr¨asentativen Beispielsanwendung veranschaulicht. Das Kapitel wird mit
einer experimentellen Untersuchung abgeschlossen, welche die Qualit¨at und
die Laufzeit der vorgestellten Algorithmen analysiert.
DieArbeitendetmiteinerZusammenfassungderwichtigsten Ergebnisse
und einem Ausblick u¨ber m¨ogliche Weiterentwicklungen.viiiContents
1 Introduction 1
2 Basics of Graph Drawing 7
2.1 Basic Terms and Concepts . . . . . . . . . . . . . . . . . . . . 7
2.1.1 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.1.2 Drawings and Planarity . . . . . . . . . . . . . . . . . 9
2.2 Requirements of Drawings . . . . . . . . . . . . . . . . . . . . 11
2.2.1 Drawing Conventions . . . . . . . . . . . . . . . . . . 12
2.2.2 Drawing Aesthetics . . . . . . . . . . . . . . . . . . . . 12
2.2.3 Drawing Constraints . . . . . . . . . . . . . . . . . . . 13
2.3 The Topology-Shape-Metrics (TSM) Approach . . . . . . . . 14
2.3.1 Planarization . . . . . . . . . . . . . . . . . . . . . . . 15
2.3.2 Orthogonalization . . . . . . . . . . . . . . . . . . . . 19
2.3.3 Compaction . . . . . . . . . . . . . . . . . . . . . . . . 23
2.4 Sugiyama’s Approach . . . . . . . . . . . . . . . . . . . . . . 25
2.4.1 Cycle Removal . . . . . . . . . . . . . . . . . . . . . . 27
2.4.2 Layer Assignment and Normalization . . . . . . . . . . 29
2.4.3 Crossing Reduction. . . . . . . . . . . . . . . . . . . . 30
2.4.4 Horizontal Coordinate Assignment . . . . . . . . . . . 31
3 Orthogonal Graph Drawing with Constraints 35
3.1 Drawing Constraints . . . . . . . . . . . . . . . . . . . . . . . 35
3.1.1 Bimodal Drawings (BIMODAL) . . . . . . . . . . . . 35
3.1.2 (Mixed) Upward Drawings (FLOW) . . . . . . . . . . 37
3.1.3 Cluster Drawings (CLUSTER) . . . . . . . . . . . . . 38
3.1.4 Partitioned Drawings (PARTITION) . . . . . . . . . . 42
3.1.5 Port/Side Preserving Drawings (PORT/SIDE) . . . . 44
3.2 Combining Drawing Constraints . . . . . . . . . . . . . . . . 47
3.2.1 Drawing Compatibilities . . . . . . . . . . . . . . . . . 48
3.2.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . 50
3.3 Constraint-Kandinsky . . . . . . . . . . . . . . . . . . . . . . 52
3.3.1 Input and Interface . . . . . . . . . . . . . . . . . . . . 53
3.3.2 Overview . . . . . . . . . . . . . . . . . . . . . . . . . 55x CONTENTS
4 Planarization with Constraints 59
4.1 The Orientation Problem . . . . . . . . . . . . . . . . . . . . 59
4.2 Mixed Upward Planarization . . . . . . . . . . . . . . . . . . 61
4.2.1 Construction of an Initial Drawing . . . . . . . . . . . 63
4.2.2 Construction of a Planar Embedding . . . . . . . . . . 66
4.2.3 Rerouting of Edges . . . . . . . . . . . . . . . . . . . . 67
4.3 Bimodal Planarization . . . . . . . . . . . . . . . . . . . . . . 68
4.4 Planarization of Clusters and Partitions . . . . . . . . . . . . 69
4.4.1 Construction of an Initial Drawing . . . . . . . . . . . 69
4.4.2 Construction of a Planar Embedding . . . . . . . . . . 76
4.4.3 Rerouting of Edges . . . . . . . . . . . . . . . . . . . . 78
4.4.4 Optimal Swimlane Order . . . . . . . . . . . . . . . . 80
4.5 Including Port and Side Constraints . . . . . . . . . . . . . . 82
4.5.1 Construction of an Initial Drawing . . . . . . . . . . . 82
4.5.2 Remaining Steps . . . . . . . . . . . . . . . . . . . . . 89
4.6 Fast Implementation of Sugiyama’s Approach . . . . . . . . . 89
4.6.1 Basic Idea . . . . . . . . . . . . . . . . . . . . . . . . . 90
4.6.2 Efficient Crossing Reduction . . . . . . . . . . . . . . 93
4.6.3 An Efficient Data Structure . . . . . . . . . . . . . . . 98
4.6.4 Runtime and Space Complexity . . . . . . . . . . . . . 101
4.6.5 Including Drawing Constraints . . . . . . . . . . . . . 101
5 Orthogonalization with Constraints 105
5.1 Tamassia’s Approach . . . . . . . . . . . . . . . . . . . . . . . 105
5.2 The Kandinsky Network . . . . . . . . . . . . . . . . . . . . . 107
5.2.1 Basic Network Formulation . . . . . . . . . . . . . . . 107
5.2.2 Incorporating Prescribed Angles and Bends . . . . . . 109
5.3 Incorporating Constraints . . . . . . . . . . . . . . . . . . . . 111
5.4 Adding Port and Side Constraints . . . . . . . . . . . . . . . 114
5.5 Handling of Self-Loops . . . . . . . . . . . . . . . . . . . . . . 117
5.6 Placement of Labels . . . . . . . . . . . . . . . . . . . . . . . 118
6 Alternatives for Realizing Port/Side Constraints 119
6.1 An Alternative Drawing Method . . . . . . . . . . . . . . . . 119
6.1.1 The Odevs Model . . . . . . . . . . . . . . . . . . . . . 120
6.1.2 Incorporating Port/Side Constraints . . . . . . . . . . 125
6.2 Alternative Planarization Approaches . . . . . . . . . . . . . 135
6.2.1 Successive Planarity Testing . . . . . . . . . . . . . . . 135
6.2.2 Spanning Tree-Based Planarization . . . . . . . . . . . 136
6.2.3 GT-Based Planarization . . . . . . . . . . . . . . . . . 136
6.3 Alternative Orthogonalization Approaches . . . . . . . . . . . 137
6.3.1 An Integer Linear Program Formulation . . . . . . . . 137
6.3.2 Orthogonalization Without Fixing a Skeleton . . . . . 139
6.4 Additional Requirements . . . . . . . . . . . . . . . . . . . . . 141

Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin