Embedding grids into grids of smaller aspect ratio

We show that 2-dimensional rectangular grid graphs can be embedded into rectangular grids of smaller aspect ratio with small expansion and dilation. In particular, width can be reduced by a factor of up to two, with optimal dilation, two. A width reduction factor of three can be obtained with optimal expansion and dilation three.

Embedding Rectangular Grids into Square Grids,
J. Ellis

IEEE Trans. on Comp., 40, pp 46 - 52, 1991.