On mapping complete binary trees into grids and extended grids - Y.-B. Lin; Zevi Miller; Manley Perkel; Dan Pritikin; Ivan Hal Sudborough (I-SPAN'99: Proceedings of the International Symposium on Parallel Architectures, Algorithms, and Networks, 1999)
We consider one-to-one, congestion one layouts of complete binary trees into 2-D grids and extended 2-D grids. For such a layout of the complete binary tree T_h of height h into the square n× n grid we consider the layout's expansion ratio r=n*n/(2^(h+1) -1). For r the least expansion among layouts of T_h into grids, we obtain the bounds 1.122<=r<=1.4656 for large h and n. For layouts into extended grids we similarly obtain bounds 1.03<=r<=1.115. The upper bounds are improvements on previous work, while the lower bounds are the first such to appear.