Computer Science – Data Structures and Algorithms
Scientific paper
2006-11-21
Computer Science
Data Structures and Algorithms
28 pages, 13 figures, 55 references, 1 appendix
Scientific paper
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}.
Buchsbaum Adam L.
Gansner Emden R.
Procopiuc Cecilia M.
Venkatasubramanian Suresh
No associations
LandOfFree
Rectangular Layouts and Contact Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Rectangular Layouts and Contact Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Rectangular Layouts and Contact Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-338552