A NEW COMBINATORIAL APPROACH TO OPTIMAL EMBEDDINGS OF RECTANGLES

An important problem in graph embeddings and parallel computing is to embed a rectangular grid into other graphs. We present a novel, genera l, combinatorial approach to (one-to-one) embedding rectangular grids into their ideal rectangular grids and optimal hypercubes. In contrast to earlier approaches of Aleliunas and Rosenberg, and Ellis, our appr oach is based on a special kind of doubly stochastic matrix. We prove that any rectangular grid can be embedded into its ideal rectangular g rid with dilation equal to the ceiling of the compression ratio, which is both optimal up to a multiplicative constant and a substantial gen eralization of previous work. We also show that any rectangular grid c an be embedded into its nearly ideal square grid with dilation at most 3. Finally, we show that any rectangular grid can be embedded into it s optimal hypercube with optimal dilation 2, a result previously obtai ned, after much research, through an ad hoc approach. Our results also imply optimal simulations of two-dimensional mesh-connected parallel machines by hypercubes and mesh-connected machines, where each process or in the guest machine is simulated by exactly one processor in the h ost.