A new lower bound for the bipartite crossing number with applications (Q1575746)

Let \(G\) be a connected bipartite graph. 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 two-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\).