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

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.