Chan, Timothy M.
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 straightline 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 straightline 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 straightline 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 straightline orderpreserving 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 straightline orthogonal orderpreserving drawing with area n2^{O(sqrt{log n})}, improving the O(n^{3/2}) previous bound by Frati (2007).
BibTeX  Entry
@InProceedings{chan:LIPIcs:2018:8736,
author = {Timothy M. Chan},
title = {{Tree Drawings Revisited}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {23:123:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770668},
ISSN = {18688969},
year = {2018},
volume = {99},
editor = {Bettina Speckmann and Csaba D. T{\'o}th},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8736},
URN = {urn:nbn:de:0030drops87364},
doi = {10.4230/LIPIcs.SoCG.2018.23},
annote = {Keywords: graph drawing, trees, recursion}
}
2018
Keywords: 

graph drawing, trees, recursion 
Seminar: 

34th International Symposium on Computational Geometry (SoCG 2018)

Issue date: 

2018 
Date of publication: 

2018 