Rectangular Layouts and Contact Graphs

Simple item page
dc.creatorBuchsbaum, Adam L.
dc.creatorGansner, Emden R.
dc.creatorProcopiuc, Cecilia M.
dc.creatorVenkatasubramanian, Suresh
dc.date2006-11-21
dc.date.accessioned2026-07-07T07:31:45Z
dc.date.available2026-07-07T07:31:45Z
dc.descriptionContact 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 $Ω(n^2)$ (rsp., $Ω(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}.
dc.description28 pages, 13 figures, 55 references, 1 appendix
dc.identifierhttps://arxiv.org/abs/cs/0611107
dc.identifierhttp://arxiv.org/abs/cs/0611107
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/118866
dc.subjectData Structures and Algorithms
dc.subjectDiscrete Mathematics
dc.subjectF.2.2; G.2.2
dc.titleRectangular Layouts and Contact Graphs
dc.typetext

Files

Collections

arXiv