Tree drawings revisited

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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

Original languageEnglish (US)
Title of host publication34th International Symposium on Computational Geometry, SoCG 2018
EditorsCsaba D. Toth, Bettina Speckmann
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages231-2315
Number of pages2085
ISBN (Electronic)9783959770668
DOIs
StatePublished - Jun 1 2018
Event34th International Symposium on Computational Geometry, SoCG 2018 - Budapest, Hungary
Duration: Jun 11 2018Jun 14 2018

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume99
ISSN (Print)1868-8969

Other

Other34th International Symposium on Computational Geometry, SoCG 2018
Country/TerritoryHungary
CityBudapest
Period6/11/186/14/18

Keywords

  • Graph drawing
  • Recursion
  • Trees

ASJC Scopus subject areas

  • Software

Cite this