Edge embedding of two-dimensional grids in hypercubes with dilation two and congestion three

Various algorithms have been proposed for embedding two-dimensional grids into optimal hyper-cubes with unit load and dilation two. All the algorithms that we have learned so far considered only node-to-node mapping. One problem with node-to-node embedding algorithms is that in congestion evaluation, one must consider all the shortest paths corresponding to guest edges that could possibly be routed through a host edge. It has been shown that two-dimensional grids can be imbedded into optimal hyper-cubes with dilation 2 and congestion 5. We present in this paper an edge embedding algorithm that maps grid edges into specific paths in an optimal hypercube. This edge embedding yields dilation 2 and congestion 3