Crossing number, pair-crossing number, and expansion (Q1880792)

The crossing number \(\text{cr}(G)\) of a graph \(G\) is the minimum possible number of edge crossings in a drawing of \(G\) in the plane, and the pair-crossing number \( \text{pcr}(G)\) of a graph \(G\) is smallest number of pairs of crossing edges in any drawing of \(G\) in the plane. It is a major problem in graph drawing if always \(\text{cr}(G)=\text{pcr}(G)\) or not. (This problem was independently raised by Mohar, and independently Pach and Tóth.) There is a very important lower bound for the crossing number in terms of bisection width: \(\text{cr}(G)=\Omega(b^2(G))-\sum_v d^2(v)\). The paper finds an analogue of this lower bound for the pair-crossing number: \(\text{pcr}(G)=\Omega(b^2(G)/\log^2 n)-\sum_v d^2(v)\). (In the formulae above, graph \(G\) has \(n\) vertices, \(b(G)\) denotes the bisection width of \(G\), and \(d(v)\) denotes the degree of vertex \(v\).) The main result of the paper is \(\text{cr}(G)=O(\log^3 n(\text{pcr}(G)+\sum_v d^2(v)))\), which is a substantial progress. The paper also shows that graphs with large crossing number have small non-planar subgraphs. The proofs use expansion and concurrent multicommodity flows.