Paper Info
Title
A Practical Algorithm for Planar Straight-line Grid Drawings of General Trees with Linear Area and Arbitrary Aspect Ratio
Abstract
Trees are usually drawn using planar straight-line drawings. [2] presented an algorithm for constructing a planar straight-line grid drawing of a degree-d(general) tree with area O(n)and any pre-specified aspect ratio in the rangewhere 0 \le1is any constant, in O(logn)time. Unfortunately, the algorithm of [2] is not suitable for practical use. The main problem is that the constant hidden in the notation for area is quite large (for binary trees was 3900). In this paper, we have made several improvements to the algorithm, which make it suitable for practical use. We have also conducted an experiment on this newer version of the algorithm for randomly-generated general trees with up to 50,000 nodes. Our experiment shows that it constructs area-efficient drawings in practice, with area at most 19 times the number of nodes.
Year
DOI
Venue
2007
10.1109/IV.2007.14
IV
Keywords
Field
DocType
planar straight-line grid drawings,practical use,linear area,binary tree,pre-specified aspect ratio,newer version,arbitrary aspect ratio,planar straight-line grid drawing,randomly-generated general tree,planar straight-line drawing,general trees,area o,main problem,practical algorithm,area-efficient drawing,visualization,engineering drawings,computer science,aspect ratio,binary trees,algorithms
Line (geometry),Notation,Combinatorics,Computer science,Algorithm,Binary tree,Planar,Grid
Conference
ISSN
ISBN
Citations 
1550-6037
0-7695-2900-3
3
PageRank 
References 
Authors
0.54
3
2
Name
Order
Citations
PageRank
Adrian Rusu18210.65
Confesor Santiago251.94