Page‐number of hypercubes and cube‐connected cycles
Michiko Konoe, Kenichi Hagihara, Nobuki Tokura · Systems and Computers in Japan · 1989
Abstract By the book embedding of a graph is meant a procedure to place the vertices of a graph along the spine of a book and to draw the edges in several pages, where the edges in a page should not cross each other. By the page‐number of a graph is meant the minimum number of pages needed in the book embedding. This paper discusses the page‐numbers of the d‐dimensional hypercube (CUBEd) and the d‐dimensional cube‐connected cycles (CCCd, h) with length h, which are considered as interesting as the processor network configuration for the parallel computer. It is already known that the upper and lower bounds of the page‐number of CUBEd(d≥1) are d and d/4, respectively. This paper shows that the page‐number of CUBEd is exactly max{d‐1, 1}, and the upper bound of the page‐number of CCCd,h (h≥3, h≥d≥1) is max{d ‐ 1, 1}. The page‐number of the graph can be utilized in the evaluation of the practical realizability of the processor network graph on WSI. In other words, the result in this paper can be used as an evaluation measure for the circuit scale, when the processor network with hypercube or cube‐connected cycles topology is to be realized on WSI.