Fraunhofer-Gesellschaft

Publica

Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

Orthogonal Compaction: Turn-Regularity, Complete Extensions, and their Common Concept

 
: Esser, Alexander M.

:

Cláudio, A.P.:
Computer Vision, Imaging and Computer Graphics Theory and Applications. 14th International Joint Conference, VISIGRAPP 2019 : Prague, Czech Republic, February 25-27, 2019, Revised Selected Papers
Cham: Springer Nature, 2020 (Communications in computer and information science 1182)
ISBN: 978-3-030-41589-1 (Print)
ISBN: 978-3-030-41590-7 (Online)
S.179-202
International Joint Conference on Computer Vision, Imaging and Computer Graphics Theory and Applications (VISIGRAPP) <14, 2019, Prague>
Englisch
Konferenzbeitrag
Fraunhofer IAIS ()
graph drawing; orthogonal drawing; compaction; turn-regularity; complete extensions

Abstract
The compaction problem in orthogonal graph drawing aims to construct efficient drawings on the orthogonal grid. The objective is to minimize the total edge length or area of a planar orthogonal grid drawing. However, any collisions, i.e. crossing edges, overlapping faces, or colliding vertices, must be avoided. The problem is NP-hard. Two common compaction methods are the turn-regularity approach by Bridgeman et al. [4] and the complete-extension approach by Klau and Mutzel [23]. Esser [14] has shown that both methods are equivalent and follow a common concept to avoid collisions. We present both approaches and their common concept in detail. We introduce an algorithm to transform the turn-regularity formulation into the complete-extension formulation and vice versa in O(n)time, where n i s the number of vertices.

: http://publica.fraunhofer.de/dokumente/N-578482.html