Efficient embeddings of trees in hypercubes

The boolean hypercube is a particularly versatile network for parallel computing. It is well known that multidimensional grid machines can be simulated on a hypercube with no communications overhead. In this paper it is shown that every bounded-degree tree can be simulated on the hypercube with constant communications overhead. In fact, the proof shows that every bounded degree graph with an O(1)-separator can be embedded in a hypercube of the same size with dilation and congestion both O(1). It is also proved that not all bounded-degree graphs can be efficiently embedded within the hypercube.