{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T18:19:31Z","timestamp":1787509171913,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540433095","type":"print"},{"value":"9783540458487","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45848-4_29","type":"book-chapter","created":{"date-parts":[[2007,8,11]],"date-time":"2007-08-11T10:47:53Z","timestamp":1186829273000},"page":"367-377","source":"Crossref","is-referenced-by-count":6,"title":["Floor-Planning via Orderly Spanning Trees"],"prefix":"10.1007","author":[{"given":"Liao","family":"Chien-Chih","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hsueh I.","family":"Lu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yen","family":"Hsu-Chun","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2002,2,21]]},"reference":[{"key":"29_CR1","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1002\/net.3230170306","volume":"17","author":"J. Bhasker","year":"1987","unstructured":"J. Bhasker and S. Sahni. A linear algorithm to check for the existence of a rectangular dual of a planar triangulated graph. Networks, 17:307\u2013317, 1987.","journal-title":"Networks"},{"key":"29_CR2","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/BF01762117","volume":"3","author":"J. Bhasker","year":"1988","unstructured":"J. Bhasker and S. Sahni. A linear algorithm to find a rectangular dual of a planar triangulated graph. Algorithmica, 3:247\u2013278, 1988.","journal-title":"Algorithmica"},{"key":"29_CR3","unstructured":"Y.-T. Chiang, C.-C. Lin, and H.-I. Lu. Orderly spanning trees with applications to graph encoding and graph drawing. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 506\u2013515, Washington, D. C., USA, 7\u20139 Jan. 2001. A revised and extended version can be found at http:\/\/xxx.lanl.gov\/abs\/cs.DS\/0102006 ."},{"key":"29_CR4","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1007\/BFb0055046","volume-title":"Compact encodings of planar graphs via canonical ordering and multiple parentheses","author":"R. C.-N. Chuang","year":"1998","unstructured":"R. C.-N. Chuang, A. Garg, X. He, M.-Y. Kao, and H.-I. Lu. Compact encodings of planar graphs via canonical ordering and multiple parentheses. In K. G. Larsen, S. Skyum, and G. Winskel, editors, Proceedings of the 25th International Colloquium on Automata, Languages, and Programming, Lecture Notes in Computer Science 1443, pages 118\u2013129, Aalborg, Denmark, 1998. Springer-Verlag."},{"key":"29_CR5","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1017\/S0963548300001139","volume":"3","author":"H. Fraysseix de","year":"1994","unstructured":"H. de Fraysseix, P. Ossona de Mendez, and P. Rosenstiehl. On triangle contact graphs. Combinatorics, Probability and Computing, 3:233\u2013246, 1994.","journal-title":"Combinatorics, Probability and Computing"},{"key":"29_CR6","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/BF02122694","volume":"10","author":"H. Fraysseix de","year":"1990","unstructured":"H. de Fraysseix, J. Pach, and R. Pollack. How to draw a planar graph on a grid. Combinatorica, 10:41\u201351, 1990.","journal-title":"Combinatorica"},{"key":"29_CR7","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1007\/3-540-62495-3_45","volume-title":"2-visibility drawings of planar graphs","author":"U. F\u00f6\u00dfmeier","year":"1997","unstructured":"U. F\u00f6\u00dfmeier, G. Kant, and M. Kaufmann. 2-visibility drawings of planar graphs. In S. North, editor, Proceedings of the 4th International Symposium on Graph Drawing, Lecture Notes in Computer Science 1190, pages 155\u2013168, California, USA, 1996. Springer-Verlag."},{"key":"29_CR8","doi-asserted-by":"publisher","first-page":"1218","DOI":"10.1137\/0222072","volume":"22","author":"X. He","year":"1993","unstructured":"X. He. On finding the rectangular duals of planar triangular graphs. SIAM Journal on Computing, 22:1218\u20131226, 1993.","journal-title":"SIAM Journal on Computing"},{"issue":"6","key":"29_CR9","doi-asserted-by":"publisher","first-page":"2150","DOI":"10.1137\/S0097539796308874","volume":"28","author":"X. He","year":"1999","unstructured":"X. He. On floor-plan of plane graphs. SIAM Journal on Computing, 28(6):2150\u20132167, 1999.","journal-title":"SIAM Journal on Computing"},{"key":"29_CR10","doi-asserted-by":"crossref","unstructured":"G. Jacobson. Space-efficient static trees and graphs. In Proceedings of the 30th Annual Symposium on Foundations of Computer Science, pages 549\u2013554, Research Triangle Park, North Carolina, 30 Oct.-1 Nov. 1989. IEEE.","DOI":"10.1109\/SFCS.1989.63533"},{"issue":"1","key":"29_CR11","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1007\/BF02086606","volume":"16","author":"G. Kant","year":"1996","unstructured":"G. Kant. Drawing planar graphs using the canonical ordering. Algorithmica, 16(1):4\u201332, 1996.","journal-title":"Algorithmica"},{"key":"29_CR12","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/S0304-3975(95)00257-X","volume":"172","author":"G. Kant","year":"1997","unstructured":"G. Kant and X. He. Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems. Theoretical Computer Science, 172(1\u20132):175\u2013193, 1997.","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"29_CR13","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1002\/net.3230150202","volume":"15","author":"K. Ko\u017ami\u0144ski","year":"1985","unstructured":"K. Ko\u017ami\u0144ski and E. Kinnen. Rectangular duals of planar graphs. Networks, 15(2):145\u2013157, 1985.","journal-title":"Networks"},{"issue":"11","key":"29_CR14","doi-asserted-by":"publisher","first-page":"1401","DOI":"10.1109\/31.14464","volume":"35","author":"K. A. K\u00f3zmi\u0144ski","year":"1988","unstructured":"K. A. K\u00f3zmi\u0144ski and E. Kinnen. Rectangular dualization and rectangular dissections. IEEE Transactions on Circuits and Systems, 35(11):1401\u20131416, 1988.","journal-title":"IEEE Transactions on Circuits and Systems"},{"issue":"4","key":"29_CR15","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1007\/BF01840399","volume":"5","author":"Y. T. Lai","year":"1990","unstructured":"Y. T. Lai and S. M. Leinwand. A theory of rectangular dual graphs. Algorithmica, 5(4):467\u2013483, 1990.","journal-title":"Algorithmica"},{"key":"29_CR16","doi-asserted-by":"crossref","unstructured":"K. Mailing, S. H. Mueller, and W. R. Heller. On finding most optimal rectangular package plans. In Proceedings of the 19th Annual IEEE Design Automation Conference, pages 263\u2013270, 1982.","DOI":"10.1109\/DAC.1982.1585567"},{"key":"29_CR17","doi-asserted-by":"crossref","unstructured":"J. I. Munro and V. Raman. Succinct representation of balanced parentheses, static trees and planar graphs. In Proceedings of the 38th Annual Symposium on Foundations of Computer Science, pages 118\u2013126, Miami Beach, Florida, 20-22 Oct. 1997. IEEE.","DOI":"10.1109\/SFCS.1997.646100"},{"key":"29_CR18","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/BF00353652","volume":"5","author":"W. Schnyder","year":"1989","unstructured":"W. Schnyder. Planar graphs and poset dimension. Order, 5:323\u2013343, 1989.","journal-title":"Order"},{"key":"29_CR19","unstructured":"W. Schnyder. Embedding planar graphs on the grid. In Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, pages 138\u2013148, 1990."},{"key":"29_CR20","doi-asserted-by":"crossref","unstructured":"S. Tsukiyama, K. Koike, and I. Shirakawa. An algorithm to eliminate all complex triangles in a maximal planar graph for use in VLSI floorplan. In Proceedings of the IEEE International Symposium on Circuits and Systems, pages 321\u2013324, 1986.","DOI":"10.1142\/9789812794468_0011"},{"issue":"3","key":"29_CR21","doi-asserted-by":"publisher","first-page":"500","DOI":"10.1137\/0222035","volume":"22","author":"K.-H. Yeap","year":"1993","unstructured":"K.-H. Yeap and M. Sarrafzadeh. Floor-planning by graph dualization: 2-concave rectilinear modules. SIAM Journal on Computing, 22(3):500\u2013526, 1993.","journal-title":"SIAM Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","Graph Drawing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45848-4_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T19:28:37Z","timestamp":1556738917000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45848-4_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540433095","9783540458487"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-45848-4_29","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2002]]}}}