Linear area upward drawings of AVL trees

被引：8

作者：

Crescenzi, P ^{[1
]}

Penna, P ^{[1
]}

Piperno, A ^{[1
]}

机构：

[1] Univ Rome La Sapienza, Dipartimento Sci Informaz, I-00198 Rome, Italy

来源：

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS | 1998年 / 9卷 / 1-2期

关键词：

graph drawing; upward drawing; area requirement;

D O I：

10.1016/S0925-7721(97)00013-8

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We prove that any AVL tree admits a linear-area straight-line strictly-upward planar grid 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. (C) 1998 Elsevier Science B.V.

引用

页码：25 / 42

页数：18

共 13 条

[1]

ADELSONVELSKII GM, 1962, SOV MATH DOKL, V3, P1259

[2]

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

[3] 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

[4]

Graham R.L., 1989, Concrete Mathematics

[5]

HORIBE Y, 1983, FIBONACCI QUART, V21, P118

[6]

HORIBE Y, 1982, FIBONACCI QUART, V20, P168

[7]

KNUTH D. E., 1975, The Art of Computer Programming. 1. Fundamental Algorithms

[8] TIDIER DRAWINGS OF TREES [J].

REINGOLD, EM ;

TILFORD, JS .

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

[9]

SHILOACH Y, 1976, THESIS WEIZMANN I SC

[10] THE COMPLEXITY OF DRAWING TREES NICELY [J].

SUPOWIT, KJ ;

REINGOLD, EM .

ACTA INFORMATICA, 1983, 18 (04) :377-392

← 1 2 →