A note on optimal area algorithms for upward drawings of binary trees - Pierluigi Crescenzi; Giuseppe Di Battista; Adolfo Piperno (Computational Geometry, 1992)
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 w(n*logn) area; this bound is tight to within a constant factor, i.e. any binary tree with n vertices can be drawn in O(n*logn) 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.