@inproceedings{c2385a08a8f947cdb043f2f81dcc6a16,

title = "Tree drawings revisited",

abstract = "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 n2O(√log lognlog log log n), improving the longstanding O(nlog n) bound; 2. every tree of size n (with arbitrarily large degree) has a straight-line upward drawing with area n√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 n2O(log∗ n), improving the previous O(nlog logn) 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 n2O(log∗ n), improving the previous O(nlog 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 n2O(√logn), improving the O(n3/2) previous bound by Frati (2007).",

keywords = "Graph drawing, Recursion, Trees",

author = "Chan, {Timothy M.}",

year = "2018",

month = jun,

day = "1",

doi = "10.4230/LIPIcs.SoCG.2018.23",

language = "English (US)",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

pages = "231--2315",

editor = "Toth, {Csaba D.} and Bettina Speckmann",

booktitle = "34th International Symposium on Computational Geometry, SoCG 2018",

note = "34th International Symposium on Computational Geometry, SoCG 2018 ; Conference date: 11-06-2018 Through 14-06-2018",

}