Publica
Hier finden Sie wissenschaftliche Publikationen aus den FraunhoferInstituten. Orthogonal Compaction: TurnRegularity, 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 2527, 2019, Revised Selected Papers Cham: Springer Nature, 2020 (Communications in computer and information science 1182) ISBN: 9783030415891 (Print) ISBN: 9783030415907 (Online) pp.179202 
 International Joint Conference on Computer Vision, Imaging and Computer Graphics Theory and Applications (VISIGRAPP) <14, 2019, Prague> 

 English 
 Conference Paper 
 Fraunhofer IAIS () 
 graph drawing; orthogonal drawing; compaction; turnregularity; 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 NPhard. Two common compaction methods are the turnregularity approach by Bridgeman et al. [4] and the completeextension 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 turnregularity formulation into the completeextension formulation and vice versa in O(n)time, where n i s the number of vertices.