MPI-INF/SWS Research Reports 1991-2021

# MPI-I-91-124

## On crossing numbers of hypercubes and cube connected cycles

### Sýkora, Ondrej and Vrto, Imrich

#### November 1991, 6 pages.

.
##### Status: available - back from printing

Recently the hypercube-like networks have received considerable attention in the field of parallel computing due to its high potential for system availability and parallel execution of algorithms. The crossing number ${\rm cr}(G)$ of a graph $G$ is defined as the least number of crossings of its edges when $G$ is drawn in a plane. Crossing numbers naturally appear in the fabrication of VLSI circuit and provide a good area lower bound argument in VLSI complexity theory. According to the survey paper of Harary et al., all that is known on the exact values of an n-dimensional hypercube ${\rm cr}(Q_n)$ is ${\rm cr}(Q_3)=0, {\rm cr}(Q_4)=8$ and ${\rm cr}(Q_5)\le 56.$ We prove the following tight bounds on ${\rm cr}(Q_n)$ and ${\rm cr}(CCC_n)$: $\frac{4^n}{20} - (n+1)2^{n-2} < {\rm cr}(Q_n) < \frac{4^n}{6} -n^22^{n-3}$ $\frac{4^n}{20} - 3(n+1)2^{n-2} < {\rm cr}(CCC_n) < \frac{4^n}{6} + 3n^22^{n-3}.$ Our lower bounds on ${\rm cr}(Q_n)$ and ${\rm cr}(CCC_n)$ give immediately alternative proofs that the area complexity of {\it hypercube} and $CCC$ computers realized on VLSI circuits is $A=\Omega (4^n)$

• 91-124.pdf
• Attachement: 91-124.pdf (9316 KBytes)

URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1991-124

BibTeX
@TECHREPORT{SykoraVrto91a,
AUTHOR = {Sýkora, Ondrej and Vrto, Imrich},
TITLE = {On crossing numbers of hypercubes and cube connected cycles},
TYPE = {Research Report},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},