MPI-INF/SWS Research Reports 1991-2021

2. Number - All Departments


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.pdf91-124.pdf
  • Attachement: 91-124.pdf (9316 KBytes)

URL to this document:

Hide details for BibTeXBibTeX
  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},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-91-124},
  MONTH = {November},
  YEAR = {1991},
  ISSN = {0946-011X},