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)
International Joint Conference on Computer Vision, Imaging and Computer Graphics Theory and Applications (VISIGRAPP) <14, 2019, Prague>
Fraunhofer IAIS ()
graph drawing; orthogonal drawing; compaction; turn-regularity; complete extensions

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.