2006/11/21 by Buchsbaum, Adam L., Gansner, Emden R., Procopiuc, Cecilia M. +1 · 1 citation
#Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #G.2.2
paper · doi:10.48550/arxiv.cs/0611107
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(n2)-area rectangular layouts for general contact graphs and O(nlog 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 Ω(n2) (rsp., Ω(nlog 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.