Tree Drawings Revisited

Research output: Contribution to journalArticlepeer-review

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(loglognlogloglogn), 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 nlogn(loglogn)O(1), improving the longstanding O(nlog 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 log n) bound; (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; (5) every binary tree of size n has a straight-line orthogonal order-preserving drawing with area n2O(logn), improving the previous O(n3 / 2) bound.

Original languageEnglish (US)
Pages (from-to)799-820
Number of pages22
JournalDiscrete and Computational Geometry
Volume63
Issue number4
DOIs
StatePublished - Jun 1 2020

Keywords

  • Graph drawing
  • Recursion
  • Trees

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Tree Drawings Revisited'. Together they form a unique fingerprint.

Cite this