Comments: The tech rep file is on hadar.
This tech report is a revised version of the tech rep number 2002-14. Please keep the
same number since we are referring to it in one of our papers. Please notice that the
title has been slightly changed also.
ContactPerson: adirusu@cse.buffalo.edu
Remote host: roc-66-66-57-100.rochester.rr.com
### Begin Citation ### Do not delete this line ###
%R 2002-14
%U /web/tech-reports/admin/hd_techrep_final.pdf
%A Garg, Ashim
%A  Rusu, Adrian
%T Straight-line Drawings of General Trees with Linear Area and Arbitrary Aspect
Ratio
%D May 16, 2003
%I Department of Computer Science and Engineering, SUNY Buffalo
%K graph drawing, straight-line, linear area
%X Trees are usually drawn planar, i.e. without any crossings.
In this paper, we investigate the area requirement of (non-upward) planar straight-
line grid
drawings of general trees.
A {\em degree-d tree} is one in which each node has at most $d$ edges incident on it.
Let $T$ be a degree-$d$ tree with $n$ nodes, such that $d =O(n^\delta)$, where $0 \le
\delta < 1/2$ is a constant.
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^{-\alpha},n^\alpha]$,
where $\alpha$ is a constant such that $0 \leq \alpha < 1$. We also show that such a
drawing can be
constructed in $O(n\log n)$ time. In particular, our result shows
that optimal area (equal to $O(n)$) and optimal aspect ratio (equal to 1)
is simultaneously achievable for such drawings.