Efficient embeddings of ternary trees into hypercubes

In this paper we present efficient graph embeddings, for complete k-ary trees into boolean hypercubes. In particular, we describe an efficient embedding of a complete ternary tree (k = 3) of height h into a hypercube, which achieves dilation 3 and expansion Theta(1.0104... (h)). The previously best-known result is dilation 2 and expansion Theta(1.333... (h)). Our embedding achieves exponentially better expansion at the cost of an increase of I in the dilation. We also describe efficient embeddings of k-ary trees into hypercubes when k = 2(p) * 3(q) for some p, q > 0 such that the embeddings achieve small constant dilation. (C) 2003 Elsevier Science (USA). All rights reserved.