Embedding a family of 2D meshes into Möbius cubes

Abstract: Möbius cubes are an important class of hypercube variants. This paper addresses how to embed a family of disjoint 2D meshes into a Möbius cube. Two major contributions of this paper are: (1) For n ≥ 1, there exists a 2 × 2n−1 mesh that can be embedded in the n-dimensional Möbius cube with dilation 1 and expansion 1. (2) For n ≥ 4, there are two disjoint 4 × 2n−3 meshes that can be embedded in the n-dimensional 0-type Möbius cube with dilation 1. The results are optimal in the sense that the dilations of the embeddings are 1. The result (2) mean that a family of two 2D-mesh-structured parallel algorithms can be operated on a same crossed cube efficiently and in parallel. Key–Words: Möbius cubes, mesh embedding, dilation, expansion, interconnection network.