Remote host: ubppp249-193.dialin.buffalo.edu
### Begin Citation ### Do not delete this line ###
%U /tmp/treedraw-prac.pdf
%A Garg, Ashim
%A Rusu, Adrian
%T A More Practical Algorithm for Drawing Binary Trees in Linear Area with ArbitraryAspect Ratio
%R 2003-12
%D September 19, 2003
%I Department of Computer Science and Engineering, SUNY Buffalo
%K tree, drawing, area, aspect ratio, straight-line, planar
%X Trees are usually drawn planar, i.e. without any edge-crossings. 
It is important to minimize the area of a drawing, so that it 
can fit within the given drawing-window. It is also important  
to give user some control over the aspect ratio of the drawing, 
so that she can display the drawing in a drawing-window with 
arbitrary width-to-height ratio. In a grid drawing, each node 
is assigned integer coordinates.   
In~\cite{gr-sldbt-02}, it was shown that any binary tree with $n$ nodes admits a planar straight-line grid drawing with area 
$O(n)$ and with any pre-specified aspect ratio in the range  
$[n^{-\epsilon},n^\epsilon]$, where $\epsilon$ is any constant such that 
$0 < \epsilon < 1$. It was  also shown that such a drawing can be 
constructed in $O(n\log n)$ time. In particular, this showed 
that optimal area (equal to $O(n)$) and optimal aspect ratio (equal to 1) 
is simultaneously achievable for such drawings.    
However, the algorithm of~\cite{gr-sldbt-02} is not suitable for practical 
use. The main problem is that the constant $c$ hidden in the ``Oh'' 
notation for area is quite large (for example, it can be as high as 3900).   
In this paper, we make several non-trivial practical improvements to 
the algorithm, which make it suitable for practical use. We have also 
conducted experiments on this newer version of the algorithm for 
randomly-generated binary trees with up to 50,000 nodes, and for complete 
binary trees with up to $65,535=2^{16}-1$ nodes. Our experiments show that 
it constructs area-efficient drawings in practice, with area at most  
8 times the number of nodes for complete binary trees, and at most  
10 times the number of nodes for randomly-generated binary trees.