The linear layout of the incomplete hypercube

In this paper, we study the linear layout problem of an incomplete hypercube by the embedding-in-book technique. An incomplete hypercube is a generalization of the hypercube in the sense that the number of nodes can be an arbitrary number. Embedding a graph in a book is to place nodes on the spine of a book and to draw the edges such that edges residing in a page do not cross. In this paper, we propose a scheme to embed an incomplete hypercube of 2ⁿ + 2^m nodes, where n > m ges 0, with n - 1 pages, cumulative page width 2ⁿ + 2^m - 3; and book width 2^{n - 1} + 2^{m - 1} for n > m > 0, 2^n-1 for n > m = 0. Moreover, this scheme can be applied to an arbitrary size of an incomplete hypercube