Paper Info
Title
Area-efficient order-preserving planar straight-line drawings of ordered trees
Abstract
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: - T admits an order-preserving planar straight-line grid drawing with O(n log n) area. - If T is a binary tree, then T admits an order-preserving planar straight-line grid drawing with O(n log log n) area. - If T is a binary tree, then T admits an order-preserving upward planar straight-line grid drawing with optimal O(n log n) area. 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 Γ 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 ≤ A ≤ n is any user-specified number. Also note that all the drawings mentioned above can be constructed in O(n) time.
Year
DOI
Venue
2003
10.1142/S021819590300130X
COCOON
Keywords
DocType
Volume
tree, drawing, order-preserving, planar, straight-line
Journal
13
Issue
ISSN
ISBN
6
0218-1959
3-540-40534-8
Citations 
PageRank 
References 
3
0.48
9
Authors
2
Name
Order
Citations
PageRank
Ashim Garg149436.84
Adrian Rusu28210.65