A near-linear area bound for drawing binary trees

被引：24

作者：

Chan, TM ^{[1
]}

机构：

[1] Univ Waterloo, Dept Comp Sci, Waterloo, ON N2L 3G1, Canada

来源：

ALGORITHMICA | 2002年 / 34卷 / 01期

关键词：

graph drawing; trees;

D O I：

10.1007/s00453-002-0937-x

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We present several simple methods to construct planar, strictly upward, strongly order-preserving, straight-line drawings of any n-node binary tree. In particular, it is shown that O (n(1+epsilon)) area is always sufficient for an arbitrary constant epsilon > 0.

引用

页码：1 / 13

页数：13

共 14 条

[1]

CHAN TM, 1997, LECT NOTES COMPUT SC, V1190, P63

[2] Linear area upward drawings of AVL trees [J].

Crescenzi, P ;

Penna, P ;

Piperno, A .

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 1998, 9 (1-2) :25-42

[3]

Crescenzi P., 1992, Computational Geometry: Theory and Applications, V2, P187, DOI 10.1016/0925-7721(92)90021-J

[4] Strictly-upward drawings of ordered search trees [J].

Crescenzi, P ;

Penna, P .

THEORETICAL COMPUTER SCIENCE, 1998, 203 (01) :51-67

[5]

DIBATTISTA G, 1998, GRAPH DRAWING

[6] Planar upward tree drawings with optimal area [J].

Garg, A ;

Goodrich, MT ;

Tamassia, R .

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 1996, 6 (03) :333-356

[7] Logarithmic width, linear area upward drawing of AVL trees [J].

Kim, SK .

INFORMATION PROCESSING LETTERS, 1997, 63 (06) :303-307

[8]

LEISERSON CE, 1980, P 21 ANN IEEE S FDN, P270

[9] TIDIER DRAWINGS OF TREES [J].

REINGOLD, EM ;

TILFORD, JS .

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, 1981, 7 (02) :223-228

[10]

SHILOACH Y, 1976, THESIS WEIZMANN I SC

← 1 2 →