1Compressing Grids into Small Hypercubes by

Let G be a graph, and denote by Q(G)/2t the hypercube of dimension log2|G|-t. Motivated by the problem of simulating large grids by small hypercubes, we construct maps f:G→Q(G)/2t, t ≥1, when G is any two or three dimensional grid, with a view to minimizing communication delay and optimizing distribution of G-processors in Q(G)/2t. Let dilation(f) = max{dist(f(x),f(y)): xy E(G)}, where "dist " denotes distance in the image network Q(G)/2t, and let the load factor of f be the maximum value of |f-1(h) | over all vertices h Q(G)/2t. Our main results are the following. (1) Let G be any two dimensional grid. Then for any t ≥1 there is a map f:G→Q(G)/2t having dilation 1 and load factor at most 1+2t. (2) Given certain upper bounds on the "densities" |G