Optimal Two-Sided Embeddings of Complete Binary Trees in Rectangular Grids

Abstract

The article considers the construction of optimal-area homeomorphic embeddings of complete binary trees in rectangular grids such that the leaf images are on the opposite sides of the grid and the edge images intersect only at node images. The minimum grid area that admits the embedding of a complete binary tree of depth n is shown to be asymptotically equal to \( \frac{n}{3}{2}^n \). An algorithm to construct an asymptotically optimal embedding of such a tree is proposed; the complexity of the algorithm is O(n2ⁿ) bit operations.