A better heuristic for area-compaction of orthogonal representations
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.
- On the complexity of orthogonal compaction
- On the complexity of orthogonal compaction
- Optimal compaction of orthogonal grid drawings. (Extended abstract)
- An experimental comparison of orthogonal compaction algorithms (extended abstract)
- Fast compaction for orthogonal drawings with vertices of prescribed size
- Optimal area-sensitive bounds for polytope approximation
- Turn-regularity and optimal area drawings of orthogonal representations
- An Exact Algorithm for Higher-Dimensional Orthogonal Packing
- Efficient algorithms for orthogonal packing problems
- Floorplans, planar graphs, and layouts
- Graph theory
- scientific article; zbMATH DE number 2123123 (Why is no real title available?)
- scientific article; zbMATH DE number 49142 (Why is no real title available?)
- On the complexity of orthogonal compaction
- Turn-regularity and optimal area drawings of orthogonal representations
- Upward drawings of triconnected digraphs.
- A framework for 1-D compaction with forbidden region avoidance
- Turn-regularity and optimal area drawings of orthogonal representations
- On the complexity of orthogonal compaction
- Fast compaction for orthogonal drawings with vertices of prescribed size
- An experimental comparison of orthogonal compaction algorithms (extended abstract)
- On Turn-Regular Orthogonal Representations
- On turn-regular orthogonal representations
- Parameterized approaches to orthogonal compaction
This page was built for publication: A better heuristic for area-compaction of orthogonal representations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2489402)