Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4637580 | Applied Mathematics and Computation | 2006 | 13 Pages |
Abstract
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%.
Related Topics
Physical Sciences and Engineering
Mathematics
Applied Mathematics
Authors
S. Mehdi Hashemi, Maryam Tahmasbi,