EMBEDDING OF GRIDS INTO OPTIMAL HYPERCUBES

This paper addresses the following graph-embedding question: given a grid and the smallest hypercube with at least as many nodes as the grid has grid points, how can grid points be assigned 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? For two-dimensional grids, a simple embedding strategy is introduced which ensures that grid-neighbors are always mapped to hypercube nodes that are within a distance of two edges of each other. Moreover, this embedding algorithm takes time linear to the number of grid points. Extending and adding further concepts, an embedding strategy is formulated for d-dimensional grids which ensures that grid-neighbors are distanced by O(d) edges in the hypercube. This algorithm takes O(d x the number of grid points) time.