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, Rome, Italy , 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
ID Code:173

Repository Staff Only: item control page

References

T. Chan, M.T. Goddrich, S.R. Kosaraju, and R. Tamassia. Optimizing Area and Aspect Ratio in Straight-Line Orthogonal Tree Drawings. In Proc. Graph Drawing 96, LNCS 1190, 63-75, 1997.

P. Crescenzi, G. Di Battista, and A. Piperno. A note on optimal area algorithms for upward drawings of binary trees. Computational Geometry: Theory and Applications, 2:187-200, 1992.

P. Crescenzi and P. Penna. Upward Drawings of Search Trees. In Proc. WG 96, LNCS 1197, 114-125, 1997.

P. Crescenzi, P. Penna, and A. Piperno. Linear area upward drawings of AVL trees. Computational Geometry: Theory and Applications, to appear.

P. Crescenzi and A. Piperno. Optimal-area upward drawings of AVL trees. In Proc. Graph Drawing 94 LNCS 894, 307-317, 1994.

P. Eades, T. Lin, and X. Lin. Minimum size h-v drawings. In Advanced Visual Interfaces, 386-394, World Scientific, 1992.

A. Garg, M.T. Goodrich, and R. Tamassia. Planar upward tree drawings with optimal area. IJCGA 6:333-356, 1996.

P.T. Metaxas, G.E. Pantziou, and A. Symvonis. Parallel h-v drawings of Binary Trees. In Proc ISAAC 94, 487-496, 1994.

Y. Shiloach. Linear and planar arrangements of graphs . Ph. D. Thesis, Department of Applied Mathematics, Weizmann Institue of Science, Rehovot, Israel, 1976.

C.-S. Shin, S.K. Kim, and K.-Y. Chwa. Area-Efficient Algorithms for Upward Straight-Line Tree Drawings. In Proc. COCOON 96, LNCS 1090, 106-116, 1996.

L. Trevisan. A Note on Minimum-Area Upward Drawing of Complete and Fibonacci Trees. Information Processing Letters, 57:231-236, 1996.