## DIMACS TR: 98-52

## A New Lower Bound for the Bipartite Crossing Number with
Applications

### Authors: Farhad Shahrokhi, Ondrej Sýkora,
László A. Székely and Imrich Vrt'o

**
ABSTRACT
**

Let $G$ be a connected bipartite graph.% on $n$-vertices.
We give a short proof, using a variation of Menger's Theorem,
for a new lower bound which relates the
*bipartite crossing number* of $G$, denoted by $bcr(G)$, to the
edge connectivity properties of $G$. The general lower bound implies
a weaker version of a very recent result, establishing a bisection
based lower bound on $bcr(G)$ which has algorithmic consequences.
Moreover, we show further applications of our general method
to estimate $bcr(G)$ for ``well structured'' families of graphs,
for which tight isoperimetric inequalities
are available. For hypercubes and 2-dimensional meshes,
the upper bounds (asymptotically) are within multiplicative factors of $4$ and $2$, from the lower bounds, respectively. The general lower bound also implies a lower bound involving eigenvalues of $G$.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1998/98-52.ps.gz

DIMACS Home Page