MinimumArea hv Drawings of Complete Binary TreesCrescenzi, P. and Penna, Paolo (1998) MinimumArea hv Drawings of Complete Binary Trees. In: Graph Drawing 5th International Symposium, GD '97, September 1820, 1997 , pp. 371382(Official URL: http://dx.doi.org/10.1007/3540639381_82). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/3540639381_82
AbstractWe study the area requirement of hv drawings of complete binary trees. An hv 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 rightwardhorizontal or a downwardvertical straightline 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 hv drawing of t is equal to (a) 2.5n4.5\sqrt{(n+1)/2}+3.5 if h is odd, (b) 2.5n3.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 minimumarea drawing of a graph has been explicitly found. Furthermore this minimumarea hv drawing can be constructed in linear time. As a consequence of this result and the result of Trevisan (1996), we have that hv drawings are provably less areaefficient than strictly upward drawings when we restrict ourselves to complete binary trees. We also give analogous results for the minimumperimeter and the minimumenclosing square area hv drawings.
Actions (login required)
