Embedding of d -dimensional grids into optimal hypercubes
M. Y. Chan · 1989
This paper addresses the following graph-embedding question: given a d-dimensional grid, and the smallest hypercube with at least as many nodes as grid points, how can we assign grid points to hypercube nodes (with at most one grid point per node) so as to keep grid-neighbors as near each other as possible in the hypercube.We give a strategy which ensures that gridneighbors are always mapped to hypercube nodes that are within a distance of O (d) edges of each other.