A Lower Bound for Dilation of an Embedding

作者：Rajan R Sundara^*; Manuel Paul; Rajasingh Indra; Parthiban N; Miller Mirka

来源：Computer Journal, 2015, 58(12): 3271-3278.

DOI：10.1093/comjnl/bxv021

• embedding
• dilation
• circulant network
• triangular grid
• Tower of Hanoi
• Sierpinski gasket graph

Graph embedding problems have gained importance in the field of interconnection networks for parallel computer architectures. Interconnection networks provide an effective mechanism for exchanging data between processors in a parallel computing system. In this paper, we introduce a technique to obtain a lower bound for dilation of an embedding. Moreover, we give algorithms to compute exact dilation of embedding circulant network into a triangular grid, Tower of Hanoi graph and Sierpinski gasket graph, proving that the lower bound obtained is sharp.

• 出版日期2015-12