Abstract
An important problem in graph embeddings and parallel computing is to embed a rectangular grid into other graphs. We present a novel, general, 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 approach is based on a special kind of doubly stochastic matrix. We prove that any rectangular grid can be embedded into its ideal rectangular grid with dilation equal to the ceiling of the compression ratio, which is bothoptimal up to a multiplicative constant and a substantial generalization of previous work. We also show that any rectangular grid can be embedded into its nearly ideal square grid with dilation at most 3. Finally, we show that any rectangular grid can be embedded into itsoptimal hypercube withoptimal dilation 2, a result previously obtained, after much research, through anad hoc approach. Our results also imply optimal simulations of two-dimensional mesh-connected parallel machines by hypercubes and mesh-connected machines, where each processor in the guest machine is simulated by exactly one processor in the host.
Similar content being viewed by others
References
R. Aleliunas and A. L. Rosenberg, On Embedding Rectangular Grids in Square Grids,IEEE Trans. Comput., Vol. 31, No. 9, pp. 907–913, 1982.
S. Bhatt, F. Chung, T. Leighton, and A. L. Rosenberg, Optimal Simulations of Tree Machines,Proc. 27th Symp. on Foundations of Computer Science, pp. 274–282, 1986.
S. Bhatt, F. Chung, T. Leighton, and A. L. Rosenberg, Efficient Embeddings of Trees in Hypercubes,SIAM J. Comput., Vol. 21, No. 1, pp. 151–162, February 1992.
M. Y. Chan, Dilation-2 Embeddings of Grids into Hypercubes,Proc. Internat. Conf. on Parallel Processing, Vol. 3, pp. 295–298, 1988.
M. Y. Chan, Embedding ofD-dimensional Grids into Optimal Hypercubes,Proc. Symp. on Parallel Algorithms and Architectures, pp. 52–57, 1989.
M. Y. Chan, Embedding Grids into Optimal Hypercubes,SIAM J. Comput., Vol. 20, No. 5, pp. 833–864, October 1991.
M. Y. Chan and F. Y. L. Chin, On Embedding Rectangular Grids in Hypercubes,IEEE Trans. Comput., Vol. 37, No. 10, pp. 1285–1288, 1988.
R. A. DeMillo, S. C. Eisenstat, and R. J. Lipton, Preserving Average Proximity in Arrays,Comm. ACM, Vol. 21, pp. 228–231, 1978.
J. A. Ellis, Embedding Rectangular Grids into Square Grids,IEEE Trans. Comput., Vol. 40, No. 1, pp. 46–52, 1991.
S. H. S. Huang, H. Liu, and R. M. Verma, On Embedding Rectangles into Optimal Squares,Proc. 22nd Internat. Conf. on Parallel Processing, Vol. III, pp. 73–76, 1993.
S. R. Kosaraju and M. J. Atallah, Optimal Simulations Between Mesh-Connected Arrays of Processors,Proc. ACM Symp. on Theory of Computing, pp. 264–272, 1986.
S. R. Kosaraju and M. J. Atallah, Optimal Simulations Between Mesh-Connected Arrays of Processors,J. Assoc. Comput. Mach., Vol. 35, pp. 635–650, 1988.
C. E. Leiserson, Area-Efficient Graph Layouts (for VLSI),Proc. 21st IEEE Symp. on Foundations of Computer Science, pp. 270–281, 1980.
R. J. Lipton, S. C. Eisenstat, and R. A. DeMillo, Space and Time Hierarchies for Classes of Control Structures and Data Structures,J. Assoc. Comput. Mach., Vol. 23, pp. 720–732, 1976.
F. Lombardi, D. Sciuto, and R. Stefanelli, An Algorithm for Functional Reconfiguration of Fixed-Size Arrays,IEEE Trans. Comput. Aided Design, Vol. 10, pp. 1114–1118, 1988.
A. L. Rosenberg and L. Snyder, Bounds on the Costs of Data Encoding,Math. Systems Theory, Vol. 12, pp. 9–39, 1978.
A. L. Rosenberg, Encoding Data Structures in Trees,J. Assoc. Comput. Mach., Vol. 26, pp. 668–689, 1979.
Author information
Authors and Affiliations
Additional information
Communicated by F. T. Leighton.
A preliminary version of this paper appeared at the IEEE International Parallel Processing Symposium, 1994. The research of the third author was supported in part by NSF Grants CCR-9010366 and CCR-9303011.
Rights and permissions
About this article
Cite this article
Huang, SH.S., Liu, H. & Verma, R.M. A New combinatorial approach to optimal embeddings of rectangles. Algorithmica 16, 161–180 (1996). https://doi.org/10.1007/BF01940645
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01940645