We consider layouts of binary trees into two and three dimensional grids with the objective to minimize the layout's expansion, where expansion is the number of grid nodes divided by the number of tree nodes. A layout is a special case of an embedding, i.e. a one-to-one mapping from tree nodes to grid nodes, such that edges of the tree are assigned to specific paths of grid edges which must not include nodes in the grid assigned to tree nodes. Furthermore, the paths assigned to tree edges in a layout must not overlap with any other such path at any node.; The results shown include (1) layouts of arbitrarily large complete binary trees into square two-dimensional grids with asymptotic expansion 1.4238 for even height and 1.4194 for odd heights, respectively, (2) layouts for arbitrarily large complete binary trees into square three dimensional grids with two layers with asymptotic expansion 1.2656 for even heights and 1.2207 for odd heights, (3) layouts for arbitrarily large complete binary trees into square three dimensional grids with six layers with asymptotic expansion 1.1719, and (4) layouts for arbitrarily large complete binary trees into three-dimensional grids with all three dimensions of approximately the same size with asymptotic expansion 1.09375. Furthermore, the techniques used for the recursive construction of these techniques may well be applicable in layouts with better expansion bounds of complete binary trees.; It is also shown that the problem of deciding if an arbitrary binary tree can be laid out in a two dimensional grid with specified dimensions is NP-Complete. No constant upper bound is known on expansion for laying out arbitrary binary trees in two dimensional grids. It is shown that any binary tree can be laid out in area O(n log n) in a two dimensional grid and with area O(n) in a two dimensional extended grid (with added diagonal connections).
展开▼
