{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,22]],"date-time":"2026-01-22T10:51:48Z","timestamp":1769079108970,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540607236","type":"print"},{"value":"9783540493518","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/bfb0021791","type":"book-chapter","created":{"date-parts":[[2005,11,13]],"date-time":"2005-11-13T06:56:38Z","timestamp":1131864998000},"page":"64-75","source":"Crossref","is-referenced-by-count":7,"title":["Optimal algorithms to embed trees in a point set"],"prefix":"10.1007","author":[{"given":"Prosenjit","family":"Bose","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"McAllister","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jack","family":"Snoeyink","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,17]]},"reference":[{"key":"8_CR1","doi-asserted-by":"crossref","unstructured":"P. Bose, G. Di Battista, W. Lenhart, and G. Liotta. Proximity constraints and representable trees. In R. Tamassia and I. G. Tollis, editors, Graph Drawing (Proc. GD '94), volume 894 of Lecture Notes in Computer Science, pages 340\u2013351. Springer-Verlag, 1995.","DOI":"10.1007\/3-540-58950-3_389"},{"key":"8_CR2","volume-title":"Report TR-SOCS-93.9","author":"P. Bose","year":"1993","unstructured":"P. Bose, W. Lenhart, and G. Liotta. Characterizing proximity trees. Report TR-SOCS-93.9, School of Comp. Sci., McGill Univ., Montreal, Quebec, Canada, 1993."},{"key":"8_CR3","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1109\/TIT.1985.1057060","volume":"IT-31","author":"B. Chazelle","year":"1985","unstructured":"B. Chazelle. On the convex layers of a planar set. IEEE Transactions on Information Theory, IT-31:509\u2013517, 1985.","journal-title":"IEEE Transactions on Information Theory"},{"key":"8_CR4","doi-asserted-by":"crossref","unstructured":"P. Crescenzi and A. Piperno. Optimal-area upward drawings of AVL trees. In R. Tamassia and I. G. Tollis, editors, Graph Drawing (Proc. GD '94), volume 894 of Lecture Notes in Computer Science, pages 307\u2013317. Springer-Verlag, 1995.","DOI":"10.1007\/3-540-58950-3_386"},{"key":"8_CR5","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/0925-7721(94)00014-X","volume":"4","author":"G. Battista Di","year":"1994","unstructured":"G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis. Algorithms for drawing graphs: an annotated bibliography. Comput. Geom. Theory Appl., 4:235\u2013282, 1994.","journal-title":"Comput. Geom. Theory Appl."},{"key":"8_CR6","doi-asserted-by":"crossref","unstructured":"P. Eades and S. Whitesides. The realization problem for Euclidean minimum spanning trees is NP-hard. In Proc. 10th Annu. ACM Sympos. Comput. Geom., pages 49\u201356, 1994.","DOI":"10.1145\/177424.177507"},{"key":"8_CR7","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/BF01994880","volume":"32","author":"J. Hershberger","year":"1992","unstructured":"J. Hershberger and S. Suri. Applications of a semi-dynamic convex hull algorithm. BIT, 32:249\u2013267, 1992.","journal-title":"BIT"},{"key":"8_CR8","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/BF02573994","volume":"11","author":"Y. Ikebe","year":"1994","unstructured":"Y. Ikebe, M. Perles, A. Tamura, and S. Tokunaga. The rooted tree embedding problem into points in the plane. Discrete & Computational Geometry, 11:51\u201363, 1994.","journal-title":"Discrete & Computational Geometry"},{"key":"8_CR9","unstructured":"G. Kant, G. Liotta, R. Tamassia, and I. Tollis. Area requirement of visibility representations of trees. In Proc. 5th Canad. Conf. Comput. Geom., pages 192\u2013197, Waterloo, Canada, 1993."},{"key":"8_CR10","unstructured":"D. E. Knuth. Fundamental Algorithms, volume 1 of The Art of Computer Programming. Addison-Wesley, second edition, 1973."},{"key":"8_CR11","first-page":"159","volume":"64","author":"J. Manning","year":"1988","unstructured":"J. Manning and M. J. Atallah. Fast detection and display of symmetry in trees. Congressus Numerantium, 64:159\u2013169, 1988.","journal-title":"Congressus Numerantium"},{"key":"8_CR12","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/0020-0190(87)90086-X","volume":"25","author":"A. Melkman","year":"1987","unstructured":"A. Melkman. On-line construction of the convex hull of a simple polyline. Information Processing Letters, 25:11\u201312, 1987.","journal-title":"Information Processing Letters"},{"key":"8_CR13","doi-asserted-by":"crossref","unstructured":"C. Monma and S. Suri. Transitions in geometric minimum spanning trees. In Proc. 7th Annu. ACM Sympos. Comput. Geom., pages 239\u2013249, 1991.","DOI":"10.1145\/109648.109675"},{"key":"8_CR14","unstructured":"A. Okabe, B. Boots, and K. Sugihara. Spatial Tessellations: Concepts and Applications of Voronoi Diagrams. John Wiley & Sons, 1992."},{"key":"8_CR15","unstructured":"J. O'Rourke. Computational Geometry in C. Cambridge University Press, 1994."},{"key":"8_CR16","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1016\/0022-0000(81)90012-X","volume":"23","author":"M. Overmars","year":"1981","unstructured":"M. Overmars and J. van Leeuwen. Maintenance of configurations in the plane. Journal of Computer and System Sciences, 23:166\u2013204, 1981.","journal-title":"Journal of Computer and System Sciences"},{"key":"8_CR17","doi-asserted-by":"crossref","unstructured":"J. Pach and J. T\u00f6r\u0151csik. Layout of rooted trees. In W. T. Trotter, editor, Planar Graphs, volume 9 of DIMACS Series, pages 131\u2013137. American Mathematical Society, 1993.","DOI":"10.1090\/dimacs\/009\/11"},{"key":"8_CR18","unstructured":"W. Paul and J. Simon. Decision trees and random access machines. Logic and Algorithmics, Monograph 30, L'Enseignement Math\u00e9matique, 1987."},{"key":"8_CR19","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry: an Introduction","author":"F. P. Preparata","year":"1985","unstructured":"F. P. Preparata and M. I. Shamos. Computational Geometry: an Introduction. Springer-Verlag, New York, NY, 1985."},{"key":"8_CR20","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/0020-0190(92)90087-C","volume":"44","author":"A. Tamura","year":"1992","unstructured":"A. Tamura and Y. Tamura. Degree constrained tree embedding into points in the plane. Information Processing Letters, 44:211\u20131214, 1992.","journal-title":"Information Processing Letters"}],"container-title":["Lecture Notes in Computer Science","Graph Drawing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0021791","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,10]],"date-time":"2020-04-10T20:50:57Z","timestamp":1586551857000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0021791"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540607236","9783540493518"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/bfb0021791","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996]]}}}