# 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.pdf | 9316 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

**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},`

` ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},`

` NUMBER = {MPI-I-91-124},`

` MONTH = {November},`

` YEAR = {1991},`

` ISSN = {0946-011X},`

`}`