Rectangular layouts and contact graphs
Open Access
- 28 March 2008
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 4 (1) , 1-28
Abstract
Contact graphs of isothetic rectangles unify many concepts from applications including VLSI and architectural design, computational geometry, and GIS. Minimizing the area of their corresponding rectangular layouts is a key problem. We study the area-optimization problem and show that it is NP-hard to find a minimum-area rectangular layout of a given contact graph. We present O ( n )-time algorithms that construct O ( n 2 )-area rectangular layouts for general contact graphs and O ( n log n )-area rectangular layouts for trees. (For trees, this is an O (log n )-approximation algorithm.) We also present an infinite family of graphs (respectively, trees) that require Ω( n 2 ) (respectively, Ω( n log n ))area. We derive these results by presenting a new characterization of graphs that admit rectangular layouts, using the related concept of rectangular duals . A corollary to our results relates the class of graphs that admit rectangular layouts to rectangle-of-influence drawings .Keywords
All Related Versions
This publication has 37 references indexed in Scilit:
- Rectangular drawings of planar graphsJournal of Algorithms, 2004
- A Simple Linear Time Algorithm for Proper Box Rectangular Drawings of Plane GraphsJournal of Algorithms, 2001
- Box-Rectangular Drawings of Plane GraphsJournal of Algorithms, 2000
- Rectangular grid drawings of plane graphsComputational Geometry, 1998
- The rectangle of influence drawability problemComputational Geometry, 1998
- Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problemsTheoretical Computer Science, 1997
- Area minimization for hierarchical floorplansAlgorithmica, 1996
- Coin graphs, Polyhedra, and conformal mappingDiscrete Mathematics, 1994
- A linear algorithm to find a rectangular dual of a planar triangulated graphAlgorithmica, 1988
- On rectangular visibilityJournal of Algorithms, 1988