Rectangular Layouts and Contact Graphs

Buchsbaum, Adam L. and Gansner, Emden R. and Procopiuc, Cecilia M. and Venkatasubramanian, Suresh (2007) Rectangular Layouts and Contact Graphs. [Journal (On-line/Unpaginated)] (Unpublished)

[img] Postscript - Requires a viewer, such as GSview
Download (440kB)


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 {\em 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 (rsp., trees) that require \Omega(n^2) (rsp., \Omega(n\log n)) area. We derive these result by presenting a new characterization of graphs that admit rectangular layouts using the related concept of {\em rectangular duals}. A corollary to our results relates the class of graphs that admit rectangular layouts to rectangle of influence drawings.

Item Type: Journal (On-line/Unpaginated)
Classifications: Z Theory > Z.500 Representations
P Styles > P.999 Others
G Algorithms and Complexity > G.560 Geometry

Actions (login required)

View Item View Item