Embedding Rectangular Grids into Square Grids with Dilation Two

摘要

In this paper, a new technique, the multiple ripple propagation technique, is presented for mapping an h x w grid into an w x h grid such that the dilation cost is 2. That is, such that any two neighboring nodes in the first grid are mapped into two nodes in the second grid that are at most distance 2 apart. This technique is then used as a basic tool for mapping any rectangular source grid into a square target grid with the dilation two property preserved. The ratio of the number of nodes in the source grid to the number of nodes in the target grid, called the expansion cost, is shown to be always less than 1.2. This is a noticeable improvement over the previously suggested techniques in which the expansion cost could be bounded by 1.2 only if the dilation cost is allowed to be as high as 18.