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

Sujets

• Informatik

Informations

• Publié par: eberhard_karls_universitat_tubingen
• Publié le: 01 janvier 2009
• Nombre de lectures: 31
• Langue: English
• Poids de l'ouvrage: 3 Mo

Extrait

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