Linear Arrangement of Incomplete Hypercubes

Y.-C. Liu, H.-W. Chang, J.-F. Fang, and C.-C. Wu (Taiwan)


Interconnection networks, incomplete hypercubes, linear arrangement, embedding in books.


In this paper, we study the linear arrangement problem of incomplete hypercubes by embedding-in-book technique. Embedding a graph in book is to arrange the vertices on a line along the spine of the book and to place the edges such that edges residing in a page do not cross. An incomplete hypercube is a generalization of the hypercubes in the sense that the number of nodes can be arbitrary number. Moreover, we can enlarge its system size without reconfiguring the links. In this paper, we arrange incomplete hypercube of 3×2n nodes on a line with n pages and 3×2n−1 book widths. Furthermore, our results have been extended to any size of incomplete hypercubes.

Important Links:

Go Back