Rectangular Layouts and Contact Graphs
<|reference_start|>Rectangular Layouts and Contact Graphs: 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 results 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 {\em rectangle of influence drawings}.<|reference_end|>
@article{buchsbaum2006rectangular,
    title={Rectangular Layouts and Contact Graphs},
    author={Adam L. Buchsbaum, Emden R. Gansner, Cecilia M. Procopiuc, Suresh
  Venkatasubramanian},
    journal={arXiv preprint arXiv:cs/0611107},
    year={2006},
    archivePrefix={arXiv},
    eprint={cs/0611107},
    primaryClass={cs.DS cs.DM}
}