A new lower bound for the bipartite crossing number with applications (Q1575746)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A new lower bound for the bipartite crossing number with applications |
scientific article |
Statements
A new lower bound for the bipartite crossing number with applications (English)
0 references
21 August 2000
0 references
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\).
0 references
bipartite crossing number
0 references
lower bounds
0 references
Menger's theorem
0 references
isoperimetric inequalities
0 references
Laplacian eigenvalues
0 references
mesh
0 references
hypercube
0 references
0 references