On embedding rectangular meshes into rectangular meshes of smaller aspect ratio

✍ Scribed by Shou-Hsuan S. Huang; Hongfei Liu; Rakesh M. Verma

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 598 KB
• Volume: 63
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(97)00114-2

✦ Synopsis

Let G = h x w be a rectangular grid and H = s x s be the optimal square grid for G, i.e., the least square grid which is no less than G in size. Let G' be the grid h' x W' such that s < W' < w and h' is the smallest integer such that hw 6 h'w'.

In this paper, a (one-to-one) embedding scheme is presented for embedding G into G' such that the dilation cost is at most 6. Previous results for this problem include a recent dilation 2 result for large compression ratios, and a dilation 3 result (through folding followed by compression) if the intermediate grid is not larger than the final host. To the best of our knowledge, this is the first result that allows to embed in the smallest square, regardless of the aspect ratio of the rectangle, while keeping the dilation constant. Our result is achieved using the compress and fold method, with a new compression method. @ 1997 Elsevier Science B.V.