Area-efficient algorithms for straight-line tree drawings

We investigate several straight-line drawing problems for bounded-degree trees in the integer grid without edge crossings under various types of drawings: (1) upward drawings whose edges are drawn as vertically monotone chains, a sequence of line segments, from a parent to its children, (2) order-preserving drawings which preserve the left-to-right order of the children of each vertex, and (3) orthogonal straight-line drawings in which each edge is represented as a single vertical or horizontal segment. Main contribution of this paper is a unified framework to reduce the upper bound on area for the straight-line drawing problems from O(n log n) (Crescenzi et al., 1992) to O(n log log n). This is the first solution of an open problem stated by Garg et al. (1993). We also show that any binary tree admits a small area drawing satisfying any given aspect ratio in the orthogonal straight-line drawing type. Our results are briefly summarized as follows. Let T be a bounded-degree tree with n vertices. Firstly, we show that T admits an upward straight-line drawing with area O(n log log n). If T is binary, we can obtain an O(n log log n)-area upward orthogonal drawing in which each edge is drawn as a chain of at most two orthogonal segments and which has O(n/log n) bends in total. Secondly, we present O(n log log n)-area (respectively, -volume) orthogonal straight-line drawing algorithms for binary trees with arbitrary aspect ratios in 2-dimension (respectively, 3-dimension). Finally, we present some experimental results which shows the area requirements, in practice, for (order-preserving) upward drawing are much smaller than theoretical bounds obtained through analysis. (C) 2000 Elsevier Science B.V. All rights reserved.
Publisher
Elsevier Science Bv
Issue Date
2000-04
Language
ENG
Keywords

AVL TREES

Citation

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, v.15, no.4, pp.175 - 202

ISSN
0925-7721
URI
http://hdl.handle.net/10203/71236
Appears in Collection
CS-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.
  • Hit : 142
  • Download : 0
  • Cited 0 times in thomson ci
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡClick to seewebofscience_button
⊙ Cited 16 items in WoSClick to see citing articles inrecords_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0