DIMACS TR: 98-52
A New Lower Bound for the Bipartite Crossing Number with
Authors: Farhad Shahrokhi, Ondrej Sýkora,
László A. Székely and Imrich Vrt'o
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:
DIMACS Home Page