Comments: The pdf file is on hadar.
The tech rep assigned number is 2003-05.
ContactPerson: adirusu@cse.buffalo.edu
Remote host: roc-66-66-57-100.rochester.rr.com
### Begin Citation ### Do not delete this line ###
%R 2003-05
%U journal.pdf
%A Garg, Ashim
%A  Rusu, Adrian
%T Area-Efficient Order-Preserving Planar Straight-line Drawings of Ordered Trees
%D May 16, 2003
%I Department of Computer Science and Engineering, SUNY Buffalo
%K graph drawing, order-preserving, straight-line
%X Ordered trees are generally drawn using order-preserving planar straight-line grid drawings. 
We therefore investigate the area-requirements of such drawings, and 
present several results:
Let $T$ be an ordered tree with $n$ nodes. Then:
\begin{itemize} 
\item $T$ admits an order-preserving  planar straight-line grid drawing with $O(n\log n)$ area. 
\item 
If $T$ is a binary tree, then $T$ admits an order-preserving  planar straight-line grid drawing with $O(n\log \log n)$ area. 
\item 
If $T$ is a binary tree, then $T$ admits an order-preserving {\em upward} planar straight-line grid drawing with {\em optimal} $O(n\log n)$ area. 
\end{itemize} 
We also study the problem of drawing  
binary trees with user-specified arbitrary aspect ratios. We show 
that an ordered binary tree $T$ with $n$ nodes admits an order-preserving  planar straight-line grid drawing $\Gamma$ with width $O(A+\log n)$, height $O((n/A)\log A)$, and area 
$O((A+\log n)(n/A)\log A)=O(n\log n)$, where $2\leq A\leq n$ is any  
user-specified number.  
Also note that all the drawings mentioned above can be  
constructed in $O(n)$ time.