A note on optimal area algorithms for upward drawings of binary trees

AbstractThe 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