Embedding Grids into Grids: Techniques for Large Compression Ratios

We return to the problem of embedding 2-dimensional (h × w ) guest grid graphs into 2dimensional (h × w ) host grid graphs, where w < w , and h is the smallest integer such that hw h w . This 2-dimensional problem has many applications in computer science including the simulation of one grid of processors by another of different shape. Also, it can likely be applied to more complex problems such as those involving grids of higher dimension and hypercubes. It is already known that optimal dilation, namely two, is always obtainable whenever w /w , the compression ratio, is no greater than two. Only a restricted set of problem instances with compression ratios greater than two could previously be solved optimally, with respect to dilation. We introduce two new techniques, called folding with compression and folding with extension. By applying folding with compression, we show that optimal solutions always exist if w ³ 7h and the remainder of h integer divided by h is no greater tha..