A Lower Bound for Dilation of an Embedding
R. Sundara Rajan, Paul D Manuel, Indra Rajasingh, N. Parthiban, Mirka Miller · The Computer Journal · 2015
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.