Straight-line Drawings of Binary Trees with Linear Area and Arbitrary Aspect Ratio

Authors

  • Ashim Garg
  • Adrian Rusu

DOI:

https://doi.org/10.7155/jgaa.00086

Abstract

Trees are usually drawn planar, i.e. without any edge-crossings. In this paper, we investigate the area requirement of (non-upward) planar straight-line grid drawings of binary trees. Let T be a binary tree with n nodes. We show that T admits a planar straight-line grid drawing with area O(n) and with any pre-specified aspect ratio in the range [n−ϵ,nϵ], where ϵ is any constant, such that 0 < ϵ < 1. We also show that such a drawing can be constructed in O(nlogn) time. In particular, our result shows that optimal area (equal to O(n)) and optimal aspect ratio (equal to 1) are simultaneously achievable for such drawings.

Downloads

Download data is not yet available.

Downloads

Published

2004-01-01

How to Cite

Garg, A., & Rusu, A. (2004). Straight-line Drawings of Binary Trees with Linear Area and Arbitrary Aspect Ratio. Journal of Graph Algorithms and Applications, 8(2), 135–160. https://doi.org/10.7155/jgaa.00086