Universität zu Köln

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.

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:	Abstract Language 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:	Creators Email ORCID ORCID Put Code Esser, Alexander M. science@alexander-esser.com orcid.org/0000-0002-5974-2637 UNSPECIFIED
URN:	urn:nbn:de:hbz:38-92405
Date:	June 2014
Place of Publication:	Köln
Language:	German
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	Data processing Computer science
Uncontrolled Keywords:	Keywords Language Orthogonal Graph Drawing English Orthogonal Drawing English Graph Drawing English Compaction English Topology Shape Metrics English Turn-Regularity English Complete Extension English Graphenzeichnen German Kompaktierung German
Date of oral exam:	May 2014
Referee:	Name Academic Title Jünger, Michael Prof. Dr.
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/9240