[author]Adam L. Buchsbaum, Emden R. Gansner, Cecilia M. Procopiuc, and Suresh Venkatasubramanian[/author].
ACM Trans. Algorithms 4, 1 (Mar. 2008), 1-28

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 (rsp., trees) that require $$\Omega(n^2)$$ (rsp., $$\Omega(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.