The goal of this paper is to investigate the area requirements for upward grid drawings of binary trees. First, we show that there is a family of binary trees with n vertices that require ω(n log n) area; this bound is tight to within a constant factor, i.e. any binary tree with n vertices can be drawn in O(n log n) area. Then we present an algorithm for constructing an upward drawing of a complete binary tree with n vertices in O(n) area, and, finally, we extend this result to the drawings of Fibonacci trees.
A NOTE ON OPTIMAL AREA ALGORITHMS FOR UPWARD DRAWINGS OF BINARY TREES / P. CRESCENZI; G. DI BATTISTA; A. PIPERNO. - In: COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS. - ISSN 0925-7721. - STAMPA. - 2:(1992), pp. 187-200. [10.1016/0925-7721(92)90021-J]
A NOTE ON OPTIMAL AREA ALGORITHMS FOR UPWARD DRAWINGS OF BINARY TREES
CRESCENZI, PIERLUIGI;
1992
Abstract
The goal of this paper is to investigate the area requirements for upward grid drawings of binary trees. First, we show that there is a family of binary trees with n vertices that require ω(n log n) area; this bound is tight to within a constant factor, i.e. any binary tree with n vertices can be drawn in O(n log n) area. Then we present an algorithm for constructing an upward drawing of a complete binary tree with n vertices in O(n) area, and, finally, we extend this result to the drawings of Fibonacci trees.
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
