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

Abstract

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
PublisherSpringer
Pages63-75
Number of pages13
ISBN (Print)3540624953, 9783540624950
DOIs
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)
Volume1190
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

OtherSymposium on Graph Drawing, GD 1996
Country/TerritoryUnited States
CityBerkeley
Period9/18/969/20/96

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

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