On the area of binary tree layouts

This note shows that it is not possible to design a complete binary tree layout with area O(n) and all leaves on the boundary, if the boundary of the chip is a convex plane curve and the leaves onThe boundary are separated by at least unit distance, then area of order nlogn is necessary just to accomodate all the wires.

Abstract

We investigate the problem of drawing an arbitrary n-node binary tree orthogonally and upwardly in an integer grid using straight-line edges. We show that one can simultaneously achieve good area bounds while also allowing the aspect ratio to be chosen as a fixed constant or a parameter under the user's control. In addition, we show that one can also achieve an additional desirable aesthetic criterion, which we call “subtree separation”. Our drawings require O(nlogn) area, which we show is optimal to within constant factors in the worst case (i.e. there are trees that need Ω(nlogn) area for any upward orthogonal straight-line drawing with good aspect ratio). An improvement for non-upward drawings is briefly mentioned.