Rectangular Layouts and Contact Graphs

Buchsbaum, Adam L. and Gansner, Emden R. and Procopiuc, Cecilia M. and Venkatasubramanian, Suresh (2007) Rectangular Layouts and Contact Graphs. [Journal (On-line/Unpaginated)] (Unpublished)

[img] Postscript - Requires a viewer, such as GSview
430Kb

Abstract

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 result 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 rectangle of influence drawings.

Item Type:Journal (On-line/Unpaginated)
Classifications:Z Theory > Z.500 Representations
P Styles > P.999 Others
G Algorithms and Complexity > G.560 Geometry
ID Code:746

Repository Staff Only: item control page

References

A. Accornero, M. Ancona, and S. Varini. All separating triangles in a plane graph can be optimally "broken" in polynomial time. International Journal of Foundations of Computer Science, 11(3):405--21, 2000.

A. V. Aho, J. E. Hopcroft, and J. D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, MA, 1974.

G. Di Battista, P. Eades, R. Tamassia, and I. Tollis. Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall, Upper Saddle River, NJ, 1999.

G. Di Battista, W. Lenhart, and G. Liotta. Proximity drawability: A survey. In Proc. Graph Drawing, DIMACS Int'l. Wks. (GD'94), volume 894 of Lecture Notes in Computer Science, pages 328-39. Springer-Verlag, 1994.

J. Bhasker and S. Sahni. A linear algorithm to find a rectangular dual of a planar triangulated graph. Algorithmica, 3:247-78, 1988.

T. Biedl, A. Bretscher, and H. Meijer. Rectangle of influence drawings of graphs without filled 3-cycles. In Proc. 7th Int'l. Symp. on Graph Drawing '99, volume 1731 of Lecture Notes in Computer Science, pages 359--68. Springer-Verlag, 1999.

T. Biedl, G. Kant, and M. Kaufmann. On triangulating planar graphs under the four-connectivity constraint. Algorithmica, 19:427-46, 1997.

A. Brandst"adt, V. B. Le, and J. P. Spinrad. Graph Classes: A Survey. SIAM Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia, PA, 1999.

M. de Berg, S. Carlsson, and M. H. Overmars. A general approach to dominance in the plane. Journal of Algorithms, 13(2):274-96, 1992.

H. de Fraysseix, P. Ossona de Mendez, and P. Rosenstiehl. On triangle contact graphs. Combinatorics, Probability and Computing, 3:233-246, 1994.

H. N. Gabow. Data structures for weighted matching and nearest common ancestors with linking. In Proc. 1st ACM-SIAM Symp. on Discrete Algorithms, pages 434-43, 1990.

K. R. Gabriel and R. R. Sokal. A new statistical approach to geographical analysis. Systematic Zoology, 18:54-64, 1969.

M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York, 1979.

D. Harel and R. E. Tarjan. Fast algorithms for finding nearest common ancestors. SIAM Journal on Computing, 13(2):338-55, 1984.

X. He. On finding the rectangular duals of planar triangular graphs. SIAM Journal on Computing, 22(6):1218-26, 1993.

X. He. A simple linear time algorithm for proper box rectangular drawings of plane graphs. Journal of Algorithms, 40(1):82-101, 2001.

P. Hlinveny. Classes and recognition of curve contact graphs. Journal of Combinatorial Theory (B), 74(1):87-103, 1998.

P. Hlinveny and J. Kratochvil. Representing graphs by disks and balls a survey of recognition-complexity results. Discrete Mathematics, 229(1-3):101-24, 2001.

J. W. Jaromczyk and G. T. Toussaint. Relative neighborhood graphs and their relatives. Proceedings of the IEEE, 80:1502-17, 1992.

G. Kant and X. He. Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems. Theoretical Computer Science, 172:175-93, 1997.

P. Koebe. Kontaktprobleme der konformen Abbildung. Berichte "uber die Verhandlungen der S"achsischen, Akad. Wiss., Math.-Phys. Klass, 88:141-64, 1936.

K. Kozminski and W. Kinnen. Rectangular duals of planar graphs. Networks, 15:145-57, 1985.

K. Kozminski and W. Kinnen. Rectangular dualization and rectangular dissections. IEEE Transactions on Circuits and Systems, 35(11):1401-16, 1988.

Y.-T. Lai and S. M. Leinwand. Algorithms for floorplan design via rectangular dualization. IEEE Transactions on Computer-Aided Design, 7:1278-89, 1988.

Y.-T. Lai and S. M. Leinwand. A theory of rectangular dual graphs. Algorithmica, 5:467-83, 1990.

A. S. LaPaugh. Algorithms for Integrated Circuit Layout: An Analytic Approach. PhD thesis, M.I.T., 1980.

G. Liotta, A. Lubiw, H. Meijer, and S. H. Whitesides. The rectangle of influence drawability problem. Computational Geometry: Theory and Applications, 10:1-22, 1998.

T. A. McKee and F. R. McMorris. Topics in Intersection Graph Theory. SIAM Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia, PA, 1999.

D. E. Muller and F. P. Preparata. Finding the intersection of two convex polyhedra. Theoretical Computer Science, 7(2):217-36, 1978.

J. R. Munkres. Topology: A First Course. Prentice-Hall of India, New Delhi, 1999.

M. H. Overmars and D. Wood. On rectangular visibility. Journal of Algorithms, 9(3):372-90, 1988.

P. Pan, W. Shi, and C. L. Liu. Area minimization for hierarchical floorplans. Algorithmica, 15:550--71, 1996.

M. Saider Rahman, S.-I. Nakano, and T. Nishizeki. Box-rectangular drawings of plane graphs. Journal of Algorithms, 37(2):363-98, 2000.

M. Saidur Rahman, S.-I. Nakano, and T. Nishizeki. Rectangular grid drawings of plane graphs. Computational Geometry: Theory and Applications, 10(3):203-20, 1998.

M. Saidur Rahman, T. Nishizeki, and S. Ghosh. Rectangular drawings of planar graphs. Journal of Algorithms, 50(1):62-78, 2004.

R. Ramakrishnan and J. Gehrke. Database Management Systems. McGraw-Hill, Boston, MA, 2000.

R. C. Read. A new method for drawing a graph given the cyclic order of the edges at each vertex. Congressus Numerantium, 56:31-44, 1987.

P. Rosenstiehl and R. E. Tarjan. Rectilinear planar layouts and bipolar orientations of planar graphs. Discrete Computational Geometry, 1:343--53, 1986.

H. Sachs. Coin graphs, polyhedra, and conformal mapping. Discrete Mathematics, 134:133-8, 1994.

B. Schieber and U. Vishkin. On finding lowest common ancestors: Simplification and parallelization. SIAM Journal on Computing, 17(6):1253-62, 1988.

W. Shi. A fast algorithm for area minimization of slicing floorplans. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 15(12):1525-32, 1996.

P. Steadman. Graph-theoretic representation of architectural arrangement. In L. March, editor, The Architecture of Form, pages 94-115. Cambridge University Press, London, New York, Melbourne, 1976.

L. Stockmeyer. Optimal orientations of cells in slicing floorplan designs. Information and Control, 57:91-101, 1983.

S. Sur-Kolay and B. B. Bhattacharya. Inherent nonslicability of rectangular duals in VLSI floorplanning. In Proc. 8th Conf. on Foundations of Software Technology and Theoretical Computer Science, volume 338 of Lecture Notes in Computer Science, pages 88-107. Springer-Verlag, 1988.

S. Sur-Kolay and B. B. Bhattacharya. On the family of inherently nonslicible floorplans in VLSI layout design. In Proc. IEEE Int'l. Conf. on Circuits and Systems, volume 5, pages 2850-3, 1991.

K. Tani, S. Tsukiyama, S. Shinoda, and I. Shirakawa. On area-efficient drawings of rectangular duals for VLSI floor-plan. Mathematical Programming, 52:29-43, 1991.

R. E. Tarjan. Applications of path compression on balanced trees. Journal of the ACM, 26(4):690-715, 1979.

C. Thomassen. Plane representations of graphs. In J. A. Bondy and U. S. R. Murty, editors, Progress in Graph Theory, pages 43-69. Academic Press, Canada, 1984.

C. Thomassen. Interval representations of planar graphs. Journal of Combinatorial Theory (B), 40:9-20, 1988.

P. Ungar. On diagrams representing maps. Journal of the London Mathematical Society, 28:336--42, 1953.

D. B. West. Introduction to Graph Theory. Prentice-Hall, Upper Saddle River, NJ, 1996.

H. Whitney. 2-isomorphic graphs. American Journal of Mathematics, 55:245-54, 1933.

S. Wimer, I. Koren, and I. Cederbaum. Floorplans, planar graphs, and layouts. IEEE Transactions on Circuits and Systems, 35(3):267-78, 1988.

G. K. Yeap and M. Sarrafzadeh. A unified approach to floorplan sizing and enumeration. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 12(12):1858-67, 1993.

G. K. Yeap and M. Sarrafzadeh. Sliceable floorplanning by graph dualization. SIAM Journal on Discrete Mathematics, 8(2):258-80, 1995.