We prove that any logarithmic binary tree admits a linear-area straight-line strictly-upward planar grid drawing (in short, 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[α]-trees admit linear-area upward drawings. We then generalize our results to logarithmic m-ary trees: as an application, we have that B-trees admit linear-area upward drawings.

UPWARD DRAWINGS OF SEARCH TREES / P. CRESCENZI; P. PENNA. - STAMPA. - (1996), pp. 114-125. (Intervento presentato al convegno TWENTY-SECOND INTERNATIONAL WORKSHOP ON GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE) [10.1007/3-540-62559-3_11].

UPWARD DRAWINGS OF SEARCH TREES

CRESCENZI, PIERLUIGI;
1996

Abstract

We prove that any logarithmic binary tree admits a linear-area straight-line strictly-upward planar grid drawing (in short, 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[α]-trees admit linear-area upward drawings. We then generalize our results to logarithmic m-ary trees: as an application, we have that B-trees admit linear-area upward drawings.
1996
Graph-Theoretic Concepts in Computer Science
TWENTY-SECOND INTERNATIONAL WORKSHOP ON GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE
P. CRESCENZI; P. PENNA
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificatore per citare o creare un link a questa risorsa: https://hdl.handle.net/2158/237694
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
social impact