Compressing grids into small hypercubes

Let G be a graph, and denote by Q(G)/2 t the hypercube of dimension ⌈log 2 | G |⌉ − t . Motivated by the problem of simulating large grids by small hypercubes, we construct maps f:G → Q(G)/2 t , t ⩾ 1 , when G is any 2‐ or 3‐dimensional grid, with a view to minimizing communication delay and optimizing distribution of G ‐processors in Q(G)/2 t , Let dilation(f) = max {dist(f(x), f(y)): xyε(G)}, where “dist” denotes distance in the image network Q(G)/2 t , and let the load factor of f be the maximum value of >f −1 (h) | over all vertices hε(G)/2 t . Our main results are the following: (1) Let G be any 2‐dimensional grid. Then, for any t ⩾ 1 , there is a map f :G → Q(G)/2 t having dilation 1 and load factor at most 1 + 2 t . (2) Given certain upper bounds on the “densities” | G|/|Q(G)/4 | or |G|/|Q(G)/8| of G in Q(G)/4 or Q(G)/8 , respectively, we get dilation 1 maps f:G → Q(G)/4 or f:G → Q(G)/8 with improved (i.e., smaller) load factor over that given in (1). (3) Let G be any 3‐dimensional grid. Then, there is a map f:G → Q(G)/2 of dilation at most 2 and load factor at most 3, and a map f:G → Q(G)/4 of dilation at most 3 and load factor at most 5.