Abstract:
Tree-like organizations are a fundamental parallel processing structure. The layout of trees has so far been studied mostly for trees of degree four or less. In this article, we give tight upper and lower bounds on the total wire length of complete m-ary trees (m>=2) on a two-dimensional grid if the leaves are constraint to lie on a grid line. For the case of m=2 we reproof an older result of Fischer and Paterson in a more direct way. The construction results in a significant reduction of the total wire length compared to the obvious ``symmetric'' layout.

Abstract:
It is shown that the total wire length of layouts of a balanced binary tree on a 2-dimensional grid can be reduced by 33% if one does not choose the obvious ``symmetric'' layout strategy. Furthermore it is shown that the more efficient layout strategy that is presented in this article is optimal, not only for binary trees but for m-ary trees with any m >= 2.