2026-07-22T05:24:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8736 2024-03-06T10:42:32Z ddc:004 open_access

Tree Drawings Revisited Chan, Timothy M. graph drawing trees recursion We make progress on a number of open problems concerning the area requirement for drawing trees on a grid. We prove that 1) every tree of size n (with arbitrarily large degree) has a straight-line drawing with area n2^{O(sqrt{log log n log log log n})}, improving the longstanding O(n log n) bound; 2) every tree of size n (with arbitrarily large degree) has a straight-line upward drawing with area n sqrt{log n}(log log n)^{O(1)}, improving the longstanding O(n log n) bound; 3) every binary tree of size n has a straight-line orthogonal drawing with area n2^{O(log^*n)}, improving the previous O(n log log n) bound by Shin, Kim, and Chwa (1996) and Chan, Goodrich, Kosaraju, and Tamassia (1996); 4) every binary tree of size n has a straight-line order-preserving drawing with area n2^{O(log^*n)}, improving the previous O(n log log n) bound by Garg and Rusu (2003); 5) every binary tree of size n has a straight-line orthogonal order-preserving drawing with area n2^{O(sqrt{log n})}, improving the O(n^{3/2}) previous bound by Frati (2007). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Timothy M. Chan 2018 Is Part Of LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2018.23 urn:nbn:de:0030-drops-87364 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.23 eng https://creativecommons.org/licenses/by/3.0/legalcode