Tighter layouts of the cube-connected cycles

AbstractÐPreparata and Vuillemin proposed the cube-connected cycles (CCC) and its compact layout in 1981 [17]. We give a new layout of the CCC which uses less than half the area of the Preparata-Vuillemin layout. We also give a lower bound on the layout area of the CCC. The area of the new layout deviates from this bound by a small constant factor. If we ªunfoldº the cycles in the CCC, the resulting structure can be laid out in optimal area. Index TermsÐInterconnection networks, cube-connected cycles, VLSI, embedding, routing, layout.