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

Timothy Chan, Michael T. Goodrich, S. Rao Kosaraju, Roberto Tamassia

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


We investigate the problem of drawing an arbitrary n-node binary tree orthogonally 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 being O(1) or sometimes even an arbitrary parameter. In addition, we show that one can also achieve an additional desirable aesthetic criterion, which we call “subtree separation,” We investigate both upward and non-upward drawings, achieving area bounds of O(n log n) and O(n log log n), respectively, and we show that, at least in the case of upward drawings, our area bound is optimal to within constant factors.

Original languageEnglish (US)
Title of host publicationGraph Drawing - Symposium on Graph Drawing, GD 1996, Proceedings
EditorsStephen North
Number of pages13
ISBN (Print)3540624953, 9783540624950
StatePublished - 1997
Externally publishedYes
EventSymposium on Graph Drawing, GD 1996 - Berkeley, United States
Duration: Sep 18 1996Sep 20 1996

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


OtherSymposium on Graph Drawing, GD 1996
Country/TerritoryUnited States

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


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