98-52: A New Lower Bound for the Bipartite Crossing Number with Applications

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