Exact Wirelength of Embedding Circulant Networks into Necklace and Windmill Graphs

Abstract

Graph embedding has been known as a powerful tool for implementation of parallel algorithms and simulation of different interconnection networks. In this paper, we obtain the minimum wirelength of embedding circulant networks into necklace and windmill graphs. The algorithms for obtaining the same are of $O(2n)$-linear time.