A new bound for the crossing number of wrapped butterflies

Abstract

We redraw the drawing of the $r$-dimensional wrapped butterfly network $WB(r)$ to get $Cr(G)\leq \frac{5}{4}4^{r}-3(2^{r})-r(2^{r})$ crossings which slightly improves the existing estimate given by Cimikowski \cite{Ci96}. We also propose a new drawing of $WB(r)$ with $Cr(G)\leq \frac{7}{8}4^{r}-(3r-4)2^{r}$ which is a finer bound.