A better heuristic for area-compaction of orthogonal representations

摘要

Area compaction of an orthogonal representation H states for computing a planar drawing of H with small area. Patrignani [On the complexity of orthogonal compaction, in: F. Dehne, A. Gupta, J.-R. Sack, R. Tamassia (Eds.), Algorithms and Data Structures, Proceedings of WADS ’99, Lecture Notes in Computer Science, vol. 1663 (1999) 56] recently proved that optimal compaction is an NP-complete problem. A turn regular orthogonal representation is an orthogonal representation that does not have a certain shape called kitty corners, [Stina S. Bridgeman, Giuseppe Di Battista, Walter Didimo, Giuseppe Liotta, Roberto Tamassia, Luca Vismara, Turn-regularity and optimal area drawings of orthogonal representations, Computational Geometry 16 (2000) 53–93]. There is a linear time algorithm with respect to the number of vertices and bends of the orthogonal representation, for optimal compaction of turn regular orthogonal representations. In this paper we present an algorithm that solves the compaction problem for general orthogonal representations in O(n3) time, where n is the number of vertices and bends. We shall show that for an orthogonal representation H with n vertices and bends and k kitty corners, if a and b stand for the height and width of the optimal area drawing of H where a ⩽ b and S′ denote the area of drawing of our algorithm, then S′/S = 1 + k/b. Experimental study shall prove that the average rate of improvement in the area of orthogonal drawing of this algorithm with respect to Heur2 [Stina S. Bridgeman, Giuseppe Di Battista, Walter Didimo, Giuseppe Liotta, Roberto Tamassia, Luca Vismara, Turn-regularity and optimal area drawings of orthogonal representations, Computational Geometry 16 (2000) 53–93] is 17%.