{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T16:35:23Z","timestamp":1770741323284,"version":"3.49.0"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2019,6,5]],"date-time":"2019-06-05T00:00:00Z","timestamp":1559692800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,6,5]],"date-time":"2019-06-05T00:00:00Z","timestamp":1559692800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1814026"],"award-info":[{"award-number":["CCF-1814026"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2020,6]]},"DOI":"10.1007\/s00454-019-00106-w","type":"journal-article","created":{"date-parts":[[2019,6,5]],"date-time":"2019-06-05T14:15:12Z","timestamp":1559744112000},"page":"799-820","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Tree Drawings Revisited"],"prefix":"10.1007","volume":"63","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8093-0675","authenticated-orcid":false,"given":"Timothy M.","family":"Chan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,6,5]]},"reference":[{"issue":"4","key":"106_CR1","doi-asserted-by":"publisher","first-page":"606","DOI":"10.1145\/1008731.1008736","volume":"51","author":"PK Agarwal","year":"2004","unstructured":"Agarwal, P.K., Har-Peled, S., Varadarajan, K.R.: Approximating extent measures of points. J. ACM 51(4), 606\u2013635 (2004). \n                  https:\/\/doi.org\/10.1145\/1008731.1008736","journal-title":"J. ACM"},{"key":"106_CR2","doi-asserted-by":"publisher","unstructured":"Bachmaier, C., Brandenburg, F.J., Brunner, W., Hofmeier, A., Matzeder, M., Unfried, T.: Tree drawings on the hexagonal grid. In: Proceedings of the 16th International Symposium on Graph Drawing (GD). Lecture Notes in Computer Science, vol. 5417, pp. 372\u2013383. Springer, Berlin (2009). \n                  https:\/\/doi.org\/10.1007\/978-3-642-00219-9_36","DOI":"10.1007\/978-3-642-00219-9_36"},{"issue":"1","key":"106_CR3","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1006\/jagm.2000.1127","volume":"38","author":"G Barequet","year":"2001","unstructured":"Barequet, G., Har-Peled, S.: Efficiently approximating the minimum-volume bounding box of a point set in three dimensions. J. Algorithms 38(1), 91\u2013109 (2001). \n                  https:\/\/doi.org\/10.1006\/jagm.2000.1127","journal-title":"J. Algorithms"},{"issue":"4","key":"106_CR4","doi-asserted-by":"publisher","first-page":"631","DOI":"10.7155\/jgaa.00432","volume":"21","author":"T Biedl","year":"2017","unstructured":"Biedl, T.: Ideal drawings of rooted trees with approximately optimal width. J. Graph Algorithms Appl. 21(4), 631\u2013648 (2017). \n                  https:\/\/doi.org\/10.7155\/jgaa.00432","journal-title":"J. Graph Algorithms Appl."},{"key":"106_CR5","unstructured":"Biedl, T.: Upward order-preserving 8-grid-drawings of binary trees. In: Proceedings of the 29th Canadian Conference on Computational Geometry (CCCG), pp. 232\u2013237 (2017). \n                  http:\/\/2017.cccg.ca\/proceedings\/Session6B-paper4.pdf"},{"issue":"1","key":"106_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-002-0937-x","volume":"34","author":"TM Chan","year":"2002","unstructured":"Chan, T.M.: A near-linear area bound for drawing binary trees. Algorithmica 34(1), 1\u201313 (2002). \n                  https:\/\/doi.org\/10.1007\/s00453-002-0937-x","journal-title":"Algorithmica"},{"issue":"2","key":"106_CR7","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/S0925-7721(01)00066-9","volume":"23","author":"TM Chan","year":"2002","unstructured":"Chan, T.M., Goodrich, M.T., Kosaraju, S.R., Tamassia, R.: Optimizing area and aspect ratio in straight-line orthogonal tree drawings. Comput. Geom. 23(2), 153\u2013162 (2002). \n                  https:\/\/doi.org\/10.1016\/S0925-7721(01)00066-9","journal-title":"Comput. Geom."},{"issue":"4","key":"106_CR8","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/0925-7721(92)90021-J","volume":"2","author":"P Crescenzi","year":"1992","unstructured":"Crescenzi, P., Di Battista, G., Piperno, A.: A note on optimal area algorithms for upward drawings of binary trees. Comput. Geom. 2(4), 187\u2013200 (1992). \n                  https:\/\/doi.org\/10.1016\/0925-7721(92)90021-J","journal-title":"Comput. Geom."},{"issue":"1","key":"106_CR9","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/S0304-3975(97)00287-9","volume":"203","author":"P Crescenzi","year":"1998","unstructured":"Crescenzi, P., Penna, P.: Strictly-upward drawings of ordered search trees. Theor. Comput. Sci. 203(1), 51\u201367 (1998). \n                  https:\/\/doi.org\/10.1016\/S0304-3975(97)00287-9","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"106_CR10","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/BF02122694","volume":"10","author":"H de Fraysseix","year":"1990","unstructured":"de Fraysseix, H., Pach, J., Pollack, R.: How to draw a planar graph on a grid. Combinatorica 10(1), 41\u201351 (1990). \n                  https:\/\/doi.org\/10.1007\/BF02122694","journal-title":"Combinatorica"},{"key":"106_CR11","doi-asserted-by":"publisher","unstructured":"Di Battista, G., Frati, F.: Drawing trees, outerplanar graphs, series-parallel graphs, and planar graphs in small area. In: Pach, J. (ed.) Thirty Essays on Geometric Graph Theory, pp. 121\u2013165. Springer, New York (2013). \n                  https:\/\/doi.org\/10.1007\/978-1-4614-0110-0_9","DOI":"10.1007\/978-1-4614-0110-0_9"},{"key":"106_CR12","volume-title":"Graph Drawing","author":"G Di Battista","year":"1999","unstructured":"Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing. Prentice Hall, Upper Saddle River (1999)"},{"key":"106_CR13","doi-asserted-by":"publisher","unstructured":"Frati, F.: Straight-line orthogonal drawings of binary and ternary trees. In: Proceedings of the 15th International Symposium on Graph Drawing (GD). Lecture Notes in Computer Science, vol. 4875, pp. 76\u201387. Springer, Berlin (2007). \n                  https:\/\/doi.org\/10.1007\/978-3-540-77537-9_11","DOI":"10.1007\/978-3-540-77537-9_11"},{"key":"106_CR14","doi-asserted-by":"publisher","unstructured":"Frati, F., Patrignani, M., Roselli, V.: LR-drawings of ordered rooted binary trees and near-linear area drawings of outerplanar graphs. In: Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1980\u20131999. SIAM, Philadelphia (2017). \n                  https:\/\/doi.org\/10.1137\/1.9781611974782.129","DOI":"10.1137\/1.9781611974782.129"},{"issue":"3","key":"106_CR15","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1142\/S0218195996000228","volume":"6","author":"A Garg","year":"1996","unstructured":"Garg, A., Goodrich, M.T., Tamassia, R.: Planar upward tree drawings with optimal area. Int. J. Comput. Geometry Appl. 6(3), 333\u2013356 (1996). \n                  https:\/\/doi.org\/10.1142\/S0218195996000228\n                  \n                . Preliminary version in SoCG\u201993","journal-title":"Int. J. Comput. Geometry Appl."},{"issue":"6","key":"106_CR16","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1142\/S021819590300130X","volume":"13","author":"A Garg","year":"2003","unstructured":"Garg, A., Rusu, A.: Area-efficient order-preserving planar straight-line drawings of ordered trees. Int. J. Comput. Geometry Appl. 13(6), 487\u2013505 (2003). \n                  https:\/\/doi.org\/10.1142\/S021819590300130X","journal-title":"Int. J. Comput. Geometry Appl."},{"key":"106_CR17","doi-asserted-by":"publisher","unstructured":"Garg, A., Rusu, A.: Straight-line drawings of general trees with linear area and arbitrary aspect ratio. In: Proceedings of the 3rd International Conference on Computational Science and Its Applications (ICCSA), Part III. Lecture Notes in Computer Science, vol. 2669, pp. 876\u2013885. Springer, Berlin (2003). \n                  https:\/\/doi.org\/10.1007\/3-540-44842-X_89","DOI":"10.1007\/3-540-44842-X_89"},{"key":"106_CR18","unstructured":"Garg, A., Rusu, A.: Straight-line drawings of binary trees with linear area and arbitrary aspect ratio. J. Graph Algorithms Appl. 8(2), 135\u2013160 (2004). \n                  http:\/\/jgaa.info\/accepted\/2004\/GargRusu2004.8.2.pdf"},{"key":"106_CR19","unstructured":"Lee, S.: Upward octagonal drawings of ternary trees. Master\u2019s thesis, University of Waterloo (2016). (Supervised by T. Biedl and T.M. Chan.) \n                  https:\/\/uwspace.uwaterloo.ca\/handle\/10012\/10832"},{"key":"106_CR20","doi-asserted-by":"publisher","unstructured":"Leiserson, C.E.: Area-efficient graph layouts (for VLSI). In: Proceedings of the 21st IEEE Symposium on Foundations of Computer Science (FOCS), pp. 270\u2013281. IEEE (1980). \n                  https:\/\/doi.org\/10.1109\/SFCS.1980.13","DOI":"10.1109\/SFCS.1980.13"},{"issue":"2","key":"106_CR21","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/BF02573972","volume":"10","author":"J Matou\u0161ek","year":"1993","unstructured":"Matou\u0161ek, J.: Range searching with efficient hierarchical cuttings. Discrete Comput. Geom. 10(2), 157\u2013182 (1993). \n                  https:\/\/doi.org\/10.1007\/BF02573972","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"106_CR22","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1109\/TSE.1981.234519","volume":"7","author":"EM Reingold","year":"1981","unstructured":"Reingold, E.M., Tilford, J.S.: Tidier drawings of trees. IEEE Trans. Softw. Eng. 7(2), 223\u2013228 (1981). \n                  https:\/\/doi.org\/10.1109\/TSE.1981.234519","journal-title":"IEEE Trans. Softw. Eng."},{"key":"106_CR23","unstructured":"Schnyder, W.: Embedding planar graphs on the grid. In: Proceedings of the 1st ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 138\u2013148. SIAM, Philadelphia (1990). \n                  http:\/\/dl.acm.org\/citation.cfm?id=320176.320191"},{"key":"106_CR24","unstructured":"Shiloach, Y.: Linear and Planar Arrangement of Graphs. Ph.D. thesis, Weizmann Institute of Science (1976). \n                  https:\/\/lib-phds1.weizmann.ac.il\/Dissertations\/shiloach_yossi.pdf"},{"issue":"4","key":"106_CR25","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/S0925-7721(99)00053-X","volume":"15","author":"C Shin","year":"2000","unstructured":"Shin, C., Kim, S.K., Chwa, K.-Y.: Area-efficient algorithms for straight-line tree drawings. Comput. Geom. 15(4), 175\u2013202 (2000). \n                  https:\/\/doi.org\/10.1016\/S0925-7721(99)00053-X\n                  \n                . Preliminary version in COCOON\u201996","journal-title":"Comput. Geom."},{"issue":"3","key":"106_CR26","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/S0020-0190(98)00049-0","volume":"66","author":"C-S Shin","year":"1998","unstructured":"Shin, C.-S., Kim, S.K., Kim, S.-H., Chwa, K.-Y.: Algorithms for drawing binary trees in the plane. Inf. Process. Lett. 66(3), 133\u2013139 (1998). \n                  https:\/\/doi.org\/10.1016\/S0020-0190(98)00049-0","journal-title":"Inf. Process. Lett."},{"issue":"5","key":"106_CR27","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/0020-0190(96)81422-0","volume":"57","author":"L Trevisan","year":"1996","unstructured":"Trevisan, L.: A note on minimum-area upward drawing of complete and Fibonacci trees. Inf. Process. Lett. 57(5), 231\u2013236 (1996). \n                  https:\/\/doi.org\/10.1016\/0020-0190(96)81422-0","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"106_CR28","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1109\/TC.1981.6312176","volume":"30","author":"LG Valiant","year":"1981","unstructured":"Valiant, L.G.: Universality considerations in VLSI circuits. IEEE Trans. Comput. 30(2), 135\u2013140 (1981). \n                  https:\/\/doi.org\/10.1109\/TC.1981.6312176","journal-title":"IEEE Trans. Comput."},{"key":"106_CR29","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, Berlin (2001). \n                  https:\/\/www.cc.gatech.edu\/fac\/Vijay.Vazirani\/book.pdf"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-019-00106-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-019-00106-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-019-00106-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,16]],"date-time":"2020-09-16T10:18:20Z","timestamp":1600251500000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-019-00106-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,5]]},"references-count":29,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,6]]}},"alternative-id":["106"],"URL":"https:\/\/doi.org\/10.1007\/s00454-019-00106-w","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,6,5]]},"assertion":[{"value":"31 December 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 May 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 May 2019","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 June 2019","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}