{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T00:13:05Z","timestamp":1725495185291},"publisher-location":"Berlin, Heidelberg","reference-count":37,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540001584"},{"type":"electronic","value":"9783540361510"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-36151-0_31","type":"book-chapter","created":{"date-parts":[[2007,11,16]],"date-time":"2007-11-16T12:14:14Z","timestamp":1195215254000},"page":"332-343","source":"Crossref","is-referenced-by-count":6,"title":["Some Applications of Orderly Spanning Trees in Graph Drawing"],"prefix":"10.1007","author":[{"given":"Ho-Lin","family":"Chen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chien-Chih","family":"Liao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hsueh-I","family":"Lu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hsu-Chun","family":"Yen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,11,8]]},"reference":[{"issue":"8","key":"31_CR1","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1109\/12.868028","volume":"49","author":"P. Bertolazzi","year":"2000","unstructured":"P. Bertolazzi, G. Di Battista, and W. Didimo. Computing orthogonal drawings with the minimum number of bends. IEEE Transactions on Computers, 49(8):826\u2013840, 2000.","journal-title":"IEEE Transactions on Computers"},{"key":"31_CR2","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/3-540-63397-9_4","volume-title":"Area-efficient static and incremental graph drawings","author":"T. Biedl","year":"1997","unstructured":"T. Biedl and M. Kaufmann. Area-efficient static and incremental graph drawings. In Proceedings of the 5th European Symposium on Algorithms, Lecture Notes in Computer Science 1284, pages 37\u201352. Springer-Verlag, 1997."},{"issue":"6","key":"31_CR3","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1142\/S0218195900000310","volume":"10","author":"T. Biedl","year":"2000","unstructured":"T. Biedl, B. Madden, and I. Tollis. The three-phase method: A unified approach to orthogonal graph drawing. International Journal of Computational Geometry and Applications, 10(6):553\u2013580, 2000.","journal-title":"International Journal of Computational Geometry and Applications"},{"key":"31_CR4","doi-asserted-by":"crossref","unstructured":"N. Bonichon, B. Le Sa\u00ebc, and M. Mosbah. Orthogonal drawings based on the stratification of planar graphs. In Proceedings of the 6th International Conference on Graph Theory, Electronic Notes in Discrete Math 5, Marseille, France, 2000. Elsevier. A full version can be found at http:\/\/citeseer.nj.nec.com\/bonichon00orthogonal.html .","DOI":"10.1016\/S1571-0653(05)80118-0"},{"key":"31_CR5","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 ."},{"issue":"3","key":"31_CR6","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1142\/S0218195997000144","volume":"7","author":"M. Chrobak","year":"1997","unstructured":"M. Chrobak and G. Kant. Convex grid drawings of 3-connected planar graphs. International Journal of Computational Geometry & Applications, 7(3):211\u2013223, 1997.","journal-title":"International Journal of Computational Geometry & Applications"},{"issue":"4","key":"31_CR7","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/0020-0190(95)00020-D","volume":"54","author":"M. Chrobak","year":"1995","unstructured":"M. Chrobak and T. H. Payne. A linear-time algorithm for drawing a planar graph on a grid. Information Processing Letters, 54(4):241\u2013246, May 1995.","journal-title":"Information Processing Letters"},{"key":"31_CR8","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":"31_CR9","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":"31_CR10","unstructured":"G. di Battista, P. Eades, R. Tammassia, and I. Tollis. Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall, 1998."},{"key":"31_CR11","doi-asserted-by":"crossref","unstructured":"M. Eiglsperger and M. Kaufmann. Fast compaction for orthogonal drawings with vertices of prescribed size. In Mutzel et al. [27], pages 124\u2013138.","DOI":"10.1007\/3-540-45848-4_11"},{"key":"31_CR12","series-title":"Lect Notes Comput Sci","first-page":"155","volume-title":"2-visibility drawings of planar graphs","author":"U. F\u00f6\\meier","year":"1997","unstructured":"U. F\u00f6\\meier, 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":"31_CR13","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1007\/BFb0021809","volume-title":"Drawing high degree graphs with low bend numbers","author":"U. F\u00f6\u00dfmeier","year":"1996","unstructured":"U. F\u00f6\u00dfmeier and M. Kaufmann. Drawing high degree graphs with low bend numbers. In S. Whitesides, editor, Proceedings of the 3th International Symposium on Graph Drawing, Lecture Notes in Computer Science 1027, pages 254\u2013266, Passau, Germany, 1995. Springer-Verlag. A full version: Technical Report WSI-95-21, Wilhelm-Schickard-Institut Universit\u00e4t T\u00fcbingen, 1995."},{"key":"31_CR14","volume-title":"Facility layout and location","author":"R. L. Francis","year":"1974","unstructured":"R. L. Francis and J. A. White. Facility layout and location. Prentice-Hall, New Jersey, 1974."},{"issue":"6","key":"31_CR15","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"},{"issue":"1","key":"31_CR16","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1006\/jagm.2001.1161","volume":"40","author":"X. He","year":"2001","unstructured":"X. He. A simple linear time algorithm for proper box rectangular drawings of plane graphs. Journal of Algorithms, 40(1):82\u2013101, 2001.","journal-title":"Journal of Algorithms"},{"key":"31_CR17","series-title":"Lect Notes Comput Sci","volume-title":"Proceedings of the 8th International Conference on Computing and Combinatorics","year":"2002","unstructured":"O. H. Ibarra and L. Zhang, editors. Proceedings of the 8th International Conference on Computing and Combinatorics, Lecture Notes in Computer Science 2387, Singapore, August 15\u201317 2002. Springer."},{"issue":"1","key":"31_CR18","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"},{"issue":"1\u20132","key":"31_CR19","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":"31_CR20","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":"31_CR21","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":"31_CR22","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":"31_CR23","doi-asserted-by":"crossref","unstructured":"C.-C. Liao, H.-I. Lu, and H.-C. Yen. Floor-planning via orderly spanning trees. In Mutzel et al. [27], pages 367\u2013377.","DOI":"10.1016\/S0196-6774(03)00057-9"},{"key":"31_CR24","doi-asserted-by":"crossref","unstructured":"H.-I. Lu. Improved compact routing tables for planar networks via orderly spanning trees. In Ibarra and Zhang [17], pages 57\u201366.","DOI":"10.1007\/3-540-45655-4_8"},{"key":"31_CR25","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":"31_CR26","series-title":"Lect Notes Comput Sci","first-page":"1043","volume-title":"Wagner\u2019s theorem on realizers","author":"M. Mosbah","year":"1998","unstructured":"M. Mosbah, N. Bonichon, and B. Le Sa\u00ebc. Wagner\u2019s theorem on realizers. In M. Hennessy and P. Widmayer, editors, Proceedings of the 29th International Colloquium on Automata, Languages, and Programming, Lecture Notes in Computer Science 1443, pages 1043\u20131063, M\u00e1laga, Spain, 2002. Springer-Verlag."},{"key":"31_CR27","series-title":"Lect Notes Comput Sci","volume-title":"Proceedings of the 9th International Symposium on Graph Drawing","year":"2002","unstructured":"P. Mutzel, M. J\u00fcnger, and S. Leipert, editors. Proceedings of the 9th International Symposium on Graph Drawing, Lecture Notes in Computer Science 2265, Vienna, Austria, 2001. Springer."},{"key":"31_CR28","doi-asserted-by":"crossref","unstructured":"P. Mutzel and R. Weiskircher. Bend minimization in orthogonal drawings using integer programming. In Ibarra and Zhang [17], pages 484\u2013493.","DOI":"10.1007\/3-540-45655-4_52"},{"key":"31_CR29","unstructured":"R. Otten. Efficient floorplan optimization. In Proceedings of International Conference on Computer Design, pages 499\u2013503, Port Chester, New York, 1983."},{"issue":"1","key":"31_CR30","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1007\/s004539910006","volume":"26","author":"A. Papakostas","year":"2000","unstructured":"A. Papakostas and I. G. Tollis. Efficient orthogonal drawings of high degree graphs. Algorithmica, 26(1):100\u2013125, 2000.","journal-title":"Algorithmica"},{"key":"31_CR31","series-title":"Lect Notes Comput Sci","first-page":"250","volume-title":"Box-rectangular drawings of plane graph","author":"M. S. Rahman","year":"1997","unstructured":"M. S. Rahman, S. Nakano, and T. Nishizeki. Box-rectangular drawings of plane graph. In Proceedings of the 21st Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science 1272, pages 250\u2013261. Springer-Verlag, 1999."},{"key":"31_CR32","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":"31_CR33","doi-asserted-by":"crossref","unstructured":"N. Sherwani. Algorithms for VLSI physical design automation. Kluwer Academic Publishers, 1995.","DOI":"10.1007\/978-1-4615-2351-2"},{"issue":"2","key":"31_CR34","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/S0019-9958(83)80038-2","volume":"57","author":"L. Stockmeyer","year":"1983","unstructured":"L. Stockmeyer. Optimal orientation of cells in slicing FLoorplan designs. Information and Control, 57(2):91\u2013101, 1983.","journal-title":"Information and Control"},{"issue":"3","key":"31_CR35","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1137\/0216030","volume":"16","author":"R. Tamassia","year":"1987","unstructured":"R. Tamassia. On embedding a graph in the grid with the minimum number of bends. SIAM Journal on Computing, 16(3):421\u2013444, 1987.","journal-title":"SIAM Journal on Computing"},{"key":"31_CR36","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":"31_CR37","doi-asserted-by":"publisher","first-page":"500","DOI":"10.1137\/0222035","volume":"22","author":"37. 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-36151-0_31","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,4]],"date-time":"2019-05-04T11:32:05Z","timestamp":1556969525000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-36151-0_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540001584","9783540361510"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/3-540-36151-0_31","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}