A More Practical Algorithm for Drawing Binary Trees in Linear Area with Arbitrary Aspect RatioGarg, Ashim and Rusu, Adrian (2004) A More Practical Algorithm for Drawing Binary Trees in Linear Area with Arbitrary Aspect Ratio. In: Graph Drawing 11th International Symposium, GD 2003, September 2124, 2003 , pp. 159165(Official URL: http://dx.doi.org/10.1007/9783540245957_15). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783540245957_15
AbstractTrees are usually drawn using planar straightline drawings. [1] presented an algorithm for constructing a planar straightline grid drawing of an nnode binary tree with area O(n) and any prespecified aspect ratio in the range [n^{\alpha}, n^{\alpha}], where 0 /le /alpha < 1 is any constant, in time. Unfortunately, the algorithm of [1] is not suitable for practical use. The main problem is that the constant hidden in the "Oh" notation for area is quite large (e.g., it can be as large as 3900). In this paper, we have made several 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 randomlygenerated and complete binary trees with up to 50,000, and 65,535 nodes, respectively. Our experiments show that it constructs areaefficient drawings in practice, with area at most 10 times and 8 times the number of nodes for randomlygenerated and complete binary trees, respectively. Research supported by NSF CAREER Award IIS9985136, NSF CISE Research Infrastructure Award No. 0101244, and Mark Diamond Research Grant No. 13Summer2003 from GSA of The State University of New York.
Actions (login required)
