Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-I-91-124

On crossing numbers of hypercubes and cube connected cycles

Sýkora, Ondrej and Vrto, Imrich

MPI-I-91-124. November 1991, 6 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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)$
Acknowledgement:
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
91-124.pdf91-124.pdf9316 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document: http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1991-124
Hide details for BibTeXBibTeX
@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},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-91-124},
  MONTH = {November},
  YEAR = {1991},
  ISSN = {0946-011X},
}