MINIMUM-AREA H-V DRAWINGS OF COMPLETE BINARY TREES

We study the area requirement of h-v drawings of complete binary trees. An h-v drawing of a binary tree t is a drawing of t such that (a) nodes are points with integer coordinates, (b) each edge is either a rightward-horizontal or a downward-vertical straight-line segment from a node to one of its children, (c) edges do not intersect, and (d) if t1 and t2 are immediate subtrees of a node u, the enclosing rectangles of the drawings of t1 and t2 are disjoint. We compute, for any complete binary tree t of height h ≥ 3 and with n nodes, the area of the optimum h-v drawing. As far as we know, this is one of the few examples in which a closed formula for the minimum-area drawing of a graph has been explicitly found. Furthermore this minimum-area h-v drawing can be constructed in linear time. As a consequence of this result and the result of Trevisan, we have that h-v drawings are provably less area-efficient than strictly upward drawings when we restrict ourselves to complete binary trees. We also give analogous results for the minimum-perimeter and the minimum-enclosing square area h-v drawings.