A better heuristic for area-compaction of orthogonal representations (Q2489402): Difference between revisions

A polynomial time algorithm for the compaction of general orthogonal representations is presented. The result of the compaction algorithm is computing an orthogonal drawing with an area smaller than a given orthogonal representation. The suggested algorithm is an extension of the algorithm Heur2 for optimal compaction of a turn regular orthogonal representation. Turn regular orthogonal representation is an orthogonal representation that does not have special corners called kitty corners. Unlike Heur2 [developed by \textit{S. S. Bridgeman, G. di Battista, W. Didimo, G. Liotta, R. Tamassia} and \textit{L. Vismara}, Comput. Geom. 16, 53--93 (2000; Zbl 0958.68528)], the algorithm presented in this article can be used in the case of general orthogonal representation that can have kitty corners. The orthogonal compaction problem belongs to the challenging tasks in the areas of VLSI (very-large-scale integrated) circuits, relationship diagrams, data flow diagrams, industrial plants, etc.