Esser, AlexanderAlexanderEsser2022-03-142022-03-142020https://publica.fraunhofer.de/handle/publica/40688910.1007/978-3-030-41590-7_8The 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.engraph drawingorthogonal drawingcompactionturn-regularitycomplete extensions005006629conference paper