A better heuristic for area-compaction of orthogonal representations

DOI10.1016/J.AMC.2005.03.007MaRDI QIDQ2489402zbMATH OpenOpenAlexFDO

Authors S. Mehdi Hashemi, Maryam Tahmasbi

Publication date 28 April 2006

Published in Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.amc.2005.03.007

zbMATH Keywords

area compactioncomplete saturatororthogonal drawingorthogonal representationplanar graphpolynomial time algorithmupward planarity

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Review text

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.

Recommendations

• On the complexity of orthogonal compaction
• scientific article; zbMATH DE number 2185601
• scientific article; zbMATH DE number 1342138
• scientific article; zbMATH DE number 2080085
• scientific article; zbMATH DE number 2084272
• 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

Cites work

• Floorplans, planar graphs, and layouts
• Graph theory
• scientific article; zbMATH DE number 2185601 (Why is no real title available?)
• scientific article; zbMATH DE number 2123123 (Why is no real title available?)
• scientific article; zbMATH DE number 49142 (Why is no real title available?)
• Turn-regularity and optimal area drawings of orthogonal representations
• Upward drawings of triconnected digraphs.

Cited in

(8)

• A framework for 1-D compaction with forbidden region avoidance
• Turn-regularity and optimal area drawings of orthogonal representations
• scientific article; zbMATH DE number 2185601 (Why is no real title available?)
• scientific article; zbMATH DE number 2084272 (Why is no real title available?)
• scientific article; zbMATH DE number 2080085 (Why is no real title available?)
• 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)