{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T12:40:12Z","timestamp":1780663212576,"version":"3.54.1"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2008,3,1]],"date-time":"2008-03-01T00:00:00Z","timestamp":1204329600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2008,3]]},"abstract":"<jats:p>\n            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\n            <jats:italic>rectangular layouts<\/jats:italic>\n            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\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            )-time algorithms that construct\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            )-area rectangular layouts for general contact graphs and\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            )-area rectangular layouts for trees. (For trees, this is an\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            )-approximation algorithm.) We also present an infinite family of graphs (respectively, trees) that require \u03a9(\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ) (respectively, \u03a9(\n            <jats:italic>n<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            ))area.\n          <\/jats:p>\n          <jats:p>\n            We derive these results by presenting a new characterization of graphs that admit rectangular layouts, using the related concept of\n            <jats:italic>rectangular duals<\/jats:italic>\n            . A corollary to our results relates the class of graphs that admit rectangular layouts to\n            <jats:italic>rectangle-of-influence drawings<\/jats:italic>\n            .\n          <\/jats:p>","DOI":"10.1145\/1328911.1328919","type":"journal-article","created":{"date-parts":[[2008,4,1]],"date-time":"2008-04-01T16:08:32Z","timestamp":1207066112000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":29,"title":["Rectangular layouts and contact graphs"],"prefix":"10.1145","volume":"4","author":[{"given":"Adam L.","family":"Buchsbaum","sequence":"first","affiliation":[{"name":"AT&amp;T Labs, Florham Park, NJ"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Emden R.","family":"Gansner","sequence":"additional","affiliation":[{"name":"AT&amp;T Labs, Florham Park, NJ"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Cecilia M.","family":"Procopiuc","sequence":"additional","affiliation":[{"name":"AT&amp;T Labs, Florham Park, NJ"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Suresh","family":"Venkatasubramanian","sequence":"additional","affiliation":[{"name":"University of Utah, Salt Lake City, UT"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2008,3,28]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1142\/S012905410000020X"},{"key":"e_1_2_1_2_1","unstructured":"Aho A. V. Hopcroft J. E. and Ullman J. D. 1974. The Design and Analysis of Computer Algorithms. Addison-Wesley Reading MA.   Aho A. V. Hopcroft J. E. and Ullman J. D. 1974. The Design and Analysis of Computer Algorithms. Addison-Wesley Reading MA."},{"key":"e_1_2_1_3_1","unstructured":"Andreev E. M. 1970a. On convex polyhedra in Lobachevski spaces. Mat. &sim;Spornik 81 123 445--478.  Andreev E. M. 1970a. On convex polyhedra in Lobachevski spaces. Mat. &sim;Spornik 81 123 445--478."},{"key":"e_1_2_1_4_1","volume-title":"On convex polyhedra of finite","author":"Andreev E. M."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01762117"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 7th International Symposium on Graph Drawing. Lecture Notes in Computer Science","volume":"1731","author":"Biedl T."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009182"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt A. Le V. B. and Spinrad J. P. 1999. Graph classes: A survey. SIAM Monographs on Discrete Mathematics and Applications. SIAM Philadelphia PA.   Brandst\u00e4dt A. Le V. B. and Spinrad J. P. 1999. Graph classes: A survey. SIAM Monographs on Discrete Mathematics and Applications. SIAM Philadelphia PA.","DOI":"10.1137\/1.9780898719796"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(92)90019-9"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300001139"},{"key":"e_1_2_1_11_1","volume-title":"Graph Drawing: Algorithms for the Visualization of Graphs","author":"Di Battista G.","year":"1999"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the DIMACS International Workshop on Graph Drawing (GD). Lecture Notes in Computer Science","volume":"894","author":"Di Battista G."},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 1st ACM-SIAM Symposium on Discrete Algorithms (SODA), 434--443","author":"Gabow H. N.","year":"1990"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.2307\/2412323"},{"key":"e_1_2_1_15_1","unstructured":"Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman New York.   Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman New York."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/0213024"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1161"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222072"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1998.1846"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(00)00204-1"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/5.163414"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(95)00257-X"},{"key":"e_1_2_1_23_1","first-page":"141","article-title":"Kontaktprobleme der konformen Abbildung. Berichte \u00fcber die Verhand-lungen der S\u00e4chsischen, Akad. Wiss","volume":"88","author":"Koebe P.","year":"1936","journal-title":"Math.-Phys. Klass"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/31.14464"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230150202"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840399"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.3167"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(97)00018-7"},{"key":"e_1_2_1_30_1","series-title":"SIAM Monographs on Discrete Mathematics and Applications","volume-title":"Topics in intersection graph theory","author":"McKee T. A."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(78)90051-8"},{"key":"e_1_2_1_32_1","volume-title":"Topology: A First Course","author":"Munkres J. R.","year":"1999"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(88)90028-4"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01940881"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00126-3"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1105"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(98)00003-0"},{"key":"e_1_2_1_38_1","unstructured":"Ramakrishnan R. and Gehrke J. 2000. Database Management Systems. McGraw-Hill Boston MA.   Ramakrishnan R. and Gehrke J. 2000. Database Management Systems. McGraw-Hill Boston MA."},{"key":"e_1_2_1_39_1","volume-title":"Congressus Numer. 56","author":"Read R. C.","year":"1987"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187706"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(93)E0068-F"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217079"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.552085"},{"key":"e_1_2_1_44_1","volume-title":"The Architecture of Form","author":"Steadman P."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(83)80038-2"},{"key":"e_1_2_1_46_1","volume-title":"Proceedings of the IEEE International Conference on Circuits and Systems","volume":"5","author":"Sur-Kolay S."},{"key":"e_1_2_1_47_1","volume-title":"Proceedings of the 8th Conference on Foundations of Software Technology and Theoretical Computer Science. Lecture Notes in Computer Science","volume":"338","author":"Sur-Kolay S."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.5555\/3113604.3113833"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/322154.322161"},{"key":"e_1_2_1_50_1","volume-title":"Progress in Graph Theory","author":"Thomassen C."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90061-4"},{"key":"e_1_2_1_52_1","volume-title":"The geometry and topology of 3-manifolds","author":"Thurston W. P."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-28.3.336"},{"key":"e_1_2_1_54_1","volume-title":"Introduction to Graph Theory","author":"West D. B."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.2307\/2371127"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/31.1739"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480191266700"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.251149"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1328911.1328919","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1328911.1328919","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:52:00Z","timestamp":1750258320000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1328911.1328919"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,3]]},"references-count":57,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,3]]}},"alternative-id":["10.1145\/1328911.1328919"],"URL":"https:\/\/doi.org\/10.1145\/1328911.1328919","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,3]]},"assertion":[{"value":"2005-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2007-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-03-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}