Esser, Alexander M. ORCID: 0000-0002-5974-2637 (2014). Kompaktierung orthogonaler Zeichnungen - Entwicklung und Analyse eines IP-basierten Algorithmus. Masters thesis, Universität zu Köln.

[img]
Preview
PDF
Masterarbeit.pdf - Accepted Version
Bereitstellung unter der CC-Lizenz: Creative Commons Attribution No Derivatives.

Download (1MB) | Preview

Abstract

Diese Arbeit befasst sich mit dem zweidimensionalen Kompaktierungsproblem für orthogonale Zeichnungen. Ziel ist es, allen Knoten Koordinaten zuzuweisen, sodass die Gesamtkantenlänge minimiert wird, die Form der Zeichnung aber erhalten bleibt. Viele Kompaktierungsheuristiken, insbesondere eindimensionale, treffen lokale Entscheidungen, beispielsweise, wie Dissecting-Kanten angeordnet werden sollen oder in welche Richtung zuerst kompaktiert wird. Ungünstige lokale Entscheidungen können jedoch zu einer höheren Gesamtkantenlänge führen. In dieser Arbeit wird daher eine zweidimensionale Kompaktierungsheuristik für 2-zusammenhängende, 4-planare Graphen vorgestellt, die die Ausrichtung der Dissecting-Kanten offen lässt und keine Richtung bevorzugt. Das Optimierungsproblem wird als IP formuliert, um die parallele Kompaktierung in beide Dimensionen zu gewährleisten. Erst beim Lösen dieses IP wird die Ausrichtung der Dissecting-Kanten festgelegt. Unter bestimmten Voraussetzungen ist die Nebenbedingungsmatrix des IP total unimodular. Eine experimentelle Analyse zeigt abschließend, dass der vorgestellte Ansatz teilweise Zeichnungen mit geringerer Gesamtkantenlänge liefert als bekannte Heuristiken.

Item Type: Thesis (Masters thesis)
Translated abstract:
AbstractLanguage
This thesis considers the two-dimensional compaction problem for orthogonal grid drawings. The task is to determine the coordinates of all vertices while preserving the shape of the drawing so that the total edge length is minimized. Many compaction heuristics, especially one-dimensional ones, make local decisions on how to arrange dissection edges or on compacting in one dimension first. These local decisions can - globally - destroy optimality. Therefore, in this thesis a two-dimensional compaction algorithm for biconnected, 4-planar graphs is presented which keeps the arrangement of dissection edges open and does not prefer any direction. The problem of minimizing the total edge length is formulated as integer linear program to ensure that the drawing is compacted in both dimensions simultaneously. The arrangement of dissection edges is not set until solving this IP in the compaction step. Under certain conditions the inequalities of the IP form a totally unimodular matrix. Finally, computational experiments show that on some instances the introduced heuristics leads to better results with respect to the total edge length than well-known heuristics.English
Creators:
CreatorsEmailORCID
Esser, Alexander M.science@alexander-esser.comorcid.org/0000-0002-5974-2637
URN: urn:nbn:de:hbz:38-92405
Subjects: Data processing Computer science
Uncontrolled Keywords:
KeywordsLanguage
Orthogonal Graph DrawingEnglish
Orthogonal DrawingEnglish
Graph DrawingEnglish
CompactionEnglish
Topology Shape MetricsEnglish
Turn-RegularityEnglish
Complete ExtensionEnglish
GraphenzeichnenGerman
KompaktierungGerman
Faculty: Faculty of Mathematics and Natural Sciences
Divisions: Faculty of Mathematics and Natural Sciences > Institute of Computer Science
Language: German
Date: June 2014
Date of oral exam: May 2014
Referee:
NameAcademic Title
Jünger, MichaelProf. Dr.
Place of Publication: Köln
Refereed: Yes
URI: http://kups.ub.uni-koeln.de/id/eprint/9240

Downloads

Downloads per month over past year

Export

Actions (login required)

View Item View Item