Minimum-Area h-v Drawings of Complete Binary Trees

Crescenzi, P. and Penna, Paolo (1998) Minimum-Area h-v Drawings of Complete Binary Trees. In: Graph Drawing 5th International Symposium, GD '97, September 18-20, 1997 , pp. 371-382(Official URL: http://dx.doi.org/10.1007/3-540-63938-1_82).

Full text not available from this repository.

Abstract

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.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-63938-1_82
Classifications: G Algorithms and Complexity > G.070 Area / Edge Length
M Methods > M.900 Tree
URI: http://gdea.informatik.uni-koeln.de/id/eprint/173

Actions (login required)

View Item View Item