TY - GEN

T1 - Tree drawings revisited

AU - Chan, Timothy M.

N1 - Publisher Copyright:
© Timothy M. Chan; licensed under Creative Commons License CC-BY 34th Symposium on Computational Geometry (SoCG 2018).

PY - 2018/6/1

Y1 - 2018/6/1

N2 - 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).

AB - 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).

KW - Graph drawing

KW - Recursion

KW - Trees

UR - http://www.scopus.com/inward/record.url?scp=85048961838&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85048961838&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.SoCG.2018.23

DO - 10.4230/LIPIcs.SoCG.2018.23

M3 - Conference contribution

AN - SCOPUS:85048961838

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 231

EP - 2315

BT - 34th International Symposium on Computational Geometry, SoCG 2018

A2 - Toth, Csaba D.

A2 - Speckmann, Bettina

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 34th International Symposium on Computational Geometry, SoCG 2018

Y2 - 11 June 2018 through 14 June 2018

ER -