A combinatorial approach to orthogonal placement problems [Elektronische Ressource] / Gunnar Werner Klau

Sujets

• Informatik

Informations

• Publié par: universitat_des_saarlandes
• Publié le: 01 janvier 2004
• Nombre de lectures: 17
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

S
S
A
A
T
R
I
A
S
V
R
A Combinatorial Approach to
Orthogonal Placement Problems
Gunnar Werner Klau
Universit t des Saarlandes
Saarbr cken, Germany
I
E
E
V
N
I
S
N
I
U
SA Combinatorial Approach to
Orthogonal Placement ProblemsS
S
A
A
T
R
I
A
S
V
R
A Combinatorial Approach to
Orthogonal Placement Problems
Gunnar Werner Klau
Dissertation
zur Erlangung des Grades
Doktor der Ingenieurwissenschaften (Dr. I ng.)
der Naturwissenschaftlich T echnischen Fakult t I
der Universit t des Saarlandes
Universit t des Saarlandes
Saarbr cken, Germany
I
E
E
V
N
I
S
N
I
U
SDatum des Kolloquiums: 3. September 2001
Dekan der Naturwissenschaftlich T echnischen Fakult t I:
Prof. Dr. Rainer Schulze P illot Z iemen
Gutachter:
Prof. Dr. Petra Mutzel, Technische Universit t Wien, sterr eich
Prof. Dr. Kurt Mehlhorn, Max Planck I nstitut f r Informatik, Saarbr ckenv
Short Abstract
We study two families of NP-hard orthogonal placement problems that arise in the area
of information visualization both from a theoretical and a practical point of view. This
thesis contains a common combinatorial framework for compaction problems in orthogo-
nal graph drawing and for point-feature labeling problems in computational cartography.
Compaction problems are concerned with performing the conversion from a dimension-
less description of the orthogonal shape of a graph to an area-eYcient drawing in the
orthogonal grid with short edges. The second family of problems deals with the task of
attaching rectangular labels to point-features such as cities or mountain peaks on a map so
that the placement results in a legible map. We present new combinatorial formulations
for these problems employing a path- and cycle-based graph-theoretic property in an asso-
ciated problem-speci c pair of constraint graphs. The reformulation allows us to develop
exact algorithms for the original problems. Extensive computational studies on real-world
benchmarks show that our linear programming based algorithms are able to solve large in-
stances of the placement problems to provable optimality within short computation time.
Furthermore, we show how to combine the formulations for compaction and labeling
problems and present an exact algorithmic approach for a graph labeling problem. Often,
our new algorithms are the rst exact algorithms for the respective problem variant.
Kurzzusammenfassung
Wir betrachten zwei Familien von NP schwierigen orthogonalen Platzierungsproblemen
aus dem Bereich der Informationsvisualisierung von einem theoretischen und praktischen
Standpunkt aus. Diese Arbeit enth lt ein gemeinsames kombinatorisches Ger st f r Kom-
paktierungsprobleme aus dem Bereich des orthogonalen Graphenzeichnens und Beschrif-
tungsprobleme von Punktmengen aus dem Gebiet der Computer Kar togra e. Bei den
Kompaktierungsproblemen geht es darum, eine gegebene dimensionslose Beschreibung
der orthogonalen Form eines Graphen in eine orthogonale Gitterzeichnung mit kurzen
Kanten und geringem Fl chenverbrauch zu transformieren. Die Beschriftungsprobleme
haben zur Aufgabe, eine gegebene Menge von rechteckigen Labels so zu platzieren, dass
eine lesbare Karte entsteht. In einer klassischen Anwendung repr sentier en die Punkte bei-
spielsweise St dte einer Landkarte, und die Labels enthalten die Namen der St dte. Wir
pr sentier en neue kombinatorische Formulierungen f r diese Probleme und verwenden
dabei eine pfad- und kreisbasierte graphentheoretische Eigenschaft in einem zugeh rigen
problemspezi schen Paar von Constraint G raphen. Die Umformulierung erm glicht es
uns, exakte Algorithmen f r die Originalprobleme zu entwickeln. Umfassende experimen-
telle Studien mit Benchmark I nstanzen aus der Praxis zeigen, dass unsere Algorithmen,
die auf linearer Programmierung beruhen, in der Lage sind, gro e Instanzen der Platzie-
rungsprobleme beweisbar optimal und in kurzer Rechenzeit zu l sen. Ferner kombinieren
wir die Formulierungen f r Kompaktierungs und Beschriftungsprobleme und pr sentie-
ren einen exakten algorithmischen Ansatz f r ein Graphbeschriftungsproblem. Oftmals
sind unsere neuen Algorithmen die ersten exakten Algorithmen f r die jeweilige Problem-
variante.vi
Acknowledgments
Many people have taught, encouraged, supported, helped, and advised me during the time
in which I worked on this thesis. I wish to express my deepest gratitude to all of them.
First of all, I would like to thank my advisor, Prof. Petra Mutzel, for providing a per-
fect balance of scienti c guidance and scienti c freedom. Petra has been a great source of
motivation and I am grateful to her for having me introduced to the fascinating research
areas of graph drawing and map labeling, for teaching me many things about combinato-
rial optimization, and for guiding my research work that led to this thesis. Setting up our
private Doktorandenseminar at MPI Saarbr cken and its continuation in Vienna proved
to be a very good idea, and I am indebted to all of its participants, in particular to RenØ
Weiskircher and Thomas Ziegler, for interesting discussions.
I also wish to thank Prof. Kurt Mehlhorn. Kurt is responsible for the highly enjoy-
able scienti c and international atmosphere at the Max Planck Institute f r Informatik in
Saarbr cken and an enthusiastic teacher. Much of what I know about algorithms and data
structures I learned in Saarbr cken and, in particular, at MPI. I consider it an honor and
privilege to have had the possibility to meet so many inspiring people in the algorithm and
complexity group of this institute and to do my rst research steps in such conducive con-
ditions. In Saarbr cken I experienced how much fun teaching can be, and I owe much
of this discovery to the diploma students I had the pleasure to advise. In particular, I
am grateful to Karsten Klein, who is also a co-author on a paper in experimental graph
drawing and who contributed to the computational study on compaction algorithms.
Particular thanks to Prof. Matteo Fischetti for helpful and enlightening discussions
concerning the relation between the zero-one and the extended polytopes, to Prof. Gerhard
Woeginger for lessons in complexity theory, to Prof. Andrew V. Goldberg for his negative
cycle detection code, and to Alexander WolV for the real-world labeling data and the
support in the conversion to our data format.
Moreover, I have appreciated the possibility of temporarily using the facilities of the
Discrete Optimization group at the University of Heidelberg, for which I would like to
thank Prof. Gerhard Reinelt and his group.
Further, I like to thank the German Federal Ministry of Research (BMBF) for nan-
cially supporting the project ?Automatisiertes Zeichnen von Zustandsgraphen , and Prof.
Ulrich Lauther, Siemens AG, for cooperation.
Thanks to my proof-readers RenØ Weiskircher, Thomas Ziegler, Sebastian Leipert,
Karsten Klein, Marco L bbecke, Birgit and Knut Reinert, Hedwig, Ragnar, and Arne
Klau, to Solofo Ramangalahy for sharing his T X wisdom, and to Martin Gruber forE
technical support.
Very special thanks to my family and to StØphanie Dagron.