Strictly-upward drawings of ordered search trees

✍ Scribed by P. Crescenzi; P. Penna

• Book ID: 104326393
• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 927 KB
• Volume: 203
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(97)00287-9

✦ Synopsis

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, redblack trees, and BB[a]-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.