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 t_{1} and t_{2} are immediate subtrees of a node u, the enclosing rectangles of the drawings of t_{1} and t_{2} are disjoint. We prove that, for any complete binary tree t of height h\geq3 and with n nodes, the area of the optimum h-v drawing of t is equal to (a) 2.5n-4.5\sqrt{(n+1)/2}+3.5 if h is odd, (b) 2.5n-3.25\sqrt{n+1}+3.5 otherwise. 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 (1996), 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