Strictly-upward drawings of ordered search trees

被引:6
作者
Crescenzi, P
Penna, P
机构
[1] Univ Florence, Dipartimento Sistemi & Informat, I-50134 Florence, Italy
[2] Univ Rome La Sapienza, Dipartimento Sci Informaz, I-00198 Rome, Italy
关键词
graph drawing; upward drawing; area requirement;
D O I
10.1016/S0304-3975(97)00287-9
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We prove that any logarithmic binary tree admits a linear-area straight-line strictly-upward planar grid drawing (in short, strictly-upward drawing), that is, a drawing in which (a) each edge is mapped into a single straight-line segment, (b) each node is placed below its parent, (c) no two edges intersect, and (d) each node is mapped into a point with integer coordinates. Informally, a logarithmic tree has the property that the height of any (sufficiently high) subtree is logarithmic with respect to the number of nodes. As a consequence, we have that k-balanced trees, red-black trees, and BB[alpha]-trees admit linear-area strictly-upward drawings. We then generalize our results to logarithmic m-ary trees: as an application, we have that B-trees admit linear-area strictly-upward drawings. (C) 1998-Elsevier Science B.V. All rights reserved.
引用
收藏
页码:51 / 67
页数:17
相关论文
共 8 条
[1]  
Crescenzi P., 1992, Computational Geometry: Theory and Applications, V2, P187, DOI 10.1016/0925-7721(92)90021-J
[2]   ALGORITHMS FOR DRAWING GRAPHS - AN ANNOTATED-BIBLIOGRAPHY [J].
DIBATTISTA, G ;
EADES, P ;
TAMASSIA, R ;
TOLLIS, IG .
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 1994, 4 (05) :235-282
[3]   UNIVERSALITY CONSIDERATIONS IN VLSI CIRCUITS [J].
VALIANT, LG .
IEEE TRANSACTIONS ON COMPUTERS, 1981, 30 (02) :135-140
[4]  
[No title captured]
[5]  
[No title captured]
[6]  
[No title captured]
[7]  
[No title captured]
[8]  
[No title captured]