Embedding multidimensional grids into optimal hypercubes

Let G and H   be graphs, with |V(H)|≥|V(G)||V(H)|≥|V(G)|, and f:V(G)→V(H)f:V(G)→V(H) a one to one map of their vertices. Let dilation(f)=max{distH(f(x),f(y)):xy∈E(G)}dilation(f)=max{distH(f(x),f(y)):xy∈E(G)}, where distH(v,w)distH(v,w) is the distance between vertices v and w of H  . Now let B(G,H)=minf{dilation(f)}B(G,H)=minf{dilation(f)}, over all such maps f.The parameter B(G,H)B(G,H) is a generalization of the classic and well studied “bandwidth” of G  , defined as B(G,P(n))B(G,P(n)), where P(n)P(n) is the path on n   points and n=|V(G)|n=|V(G)|. Let [a1×a2×⋯×ak][a1×a2×⋯×ak] be the k  -dimensional grid graph with integer values 1 through aiai in the i  'th coordinate. In this paper, we study B(G,H)B(G,H) in the case when G=[a1×a2×⋯×ak]G=[a1×a2×⋯×ak] and H   is the hypercube QnQn of dimension n=⌈log2(|V(G)|)⌉n=⌈log2(|V(G)|)⌉, the hypercube of smallest dimension having at least as many points as G. Our main result is thatB([a1×a2×⋯×ak],Qn)≤3k,B([a1×a2×⋯×ak],Qn)≤3k, provided ai≥222ai≥222 for each 1≤i≤k1≤i≤k. For such G, the bound 3k   improves on the previous best upper bound 4k+O(1)4k+O(1). Our methods include an application of Knuth's result on two-way rounding and of the existence of spanning regular cyclic caterpillars in the hypercube.