Embedding 2-Dimensional Grids Into Optimal Hypercubes with Edge-Congestion 1 or 2
Markus Röttger, Ulf-Peter Schroeder · Parallel Processing Letters · 1998
This paper explores one-to-one embeddings of 2-dimensional grids into hypercubes. It is shown that each 2-dimensional grid can be embedded with edge-congestion 2 into its optimal hypercube (the smallest hypercube with at least as many nodes as the grid). Additionally, a technique is developed to embed many 2-dimensional grids into their optimal hypercubes with edge-congestion 1.