Efficient embeddings of grids into grids

In this paper we explore one-to-one embeddings of two-dimensional grids int o their ideal two-dimensional grids. The presented results are optimal or c onsiderably close to the optimum. For embedding grids into grids of smaller aspect ratio, we prove a new lower bound on the dilation matching a known upper bound. The edge-congestion provided by our matrix-based construction differs from the here presented lower bound by at most one. For embedding g rids into grids of larger aspect ratio, we establish five as an upper bound on the dilation and four as an upper bound on the edge-congestion, which a re improvements over previous results. (C) 2001 Elsevier Science B.V. All r ights reserved.