Optimizing area and aspect ratio in straight-line orthogonal tree drawings

Timothy M. Chan, Michael T. Goodrich, S. Rao Kosaraju, Roberta Tamassia

Research output: Contribution to journalArticlepeer-review

Abstract

We investigate the problem of drawing an arbitrary «-node binary tree orthogonally and upwardly in an integer grid using straight-line edges. We show that one can simultaneously achieve good area bounds while also allowing the aspect ratio to be chosen as a fixed constant or a parameter under the user's control. In addition, we show that one can also achieve an additional desirable aesthetic criterion, which we call "subtree separation". Our drawings require O(;i log«) area, which we show is optimal to within constant factors in the worst case (i.e. there are trees that need £2 (H log«) area for any upward orthogonal straight-line drawing with good aspect ratio). An improvement for non-upward drawings is briefly mentioned.

Original languageEnglish (US)
Pages (from-to)153-162
Number of pages10
JournalComputational Geometry: Theory and Applications
Volume23
Issue number2
DOIs
StatePublished - 2002
Externally publishedYes

Keywords

  • Binary trees
  • Graph drawing

ASJC Scopus subject areas

  • Computer Science Applications
  • Geometry and Topology
  • Control and Optimization
  • Computational Theory and Mathematics
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Optimizing area and aspect ratio in straight-line orthogonal tree drawings'. Together they form a unique fingerprint.

Cite this