Embedding of Meshes on Rotator Graphs1

Abstract- A set of directed permutation graphs called rotator graphs were proposed as an alternative to the star and pancake graphs for multiprocessor interconnection networks. The rotator graphs have a smaller diameter than star and pancake graphs for the same num-ber of nodes. while sharing the properties of star, pancake, and bina-ry hypercubes like maximal fault tolerance, partitionability, etc. In this paper we develop a class of algorithms for recognizing undirected mesh structures in n-rotator graphs. The average dilation of the em-beddings are very low as compared to the dilation of the embedding. These embeddings will he very useful for regular computations with bi-directional requirements, in addition to the irregular computations in n-rotator graphs. Most of the results presented here equally apply to another set of directed Cayley graphs, the cycle prefix digraphs