On the decay of crossing numbers (Q2464150)

Let \(\text{cr}(G)\) denote the crossing number of the graph \(G\). \textit{B. Richter} and \textit{C. Thomassen} [J. Comb. Theory, Ser. B 58, 217--224 (1993; Zbl 0733.05035)] conjectured that there is a constant \(c\) such that every graph \(G\) with crossing number \(k\) has an edge \(e\) such that \(\text{cr}(G-e)\geq k-c\sqrt{k}\), and showed that there is always an edge \(e\) such that \(\text{cr}(G-e)\geq 0.4k-O(1)\). The present paper shows that for every fixed \(\varepsilon>0\) there is a constant \(n_0\) depending on \(\varepsilon\) such that every graph graph \(G\) of order \(n>n_0\) and size \(m>n^{1+\varepsilon}\) has a subgraph \(G'\) with at most \((1-\varepsilon/24)m \) edges, such that \(\text{cr}(G') > ({1\over 28}-o(1))\text{cr}(G)\). The proofs revisit the bisection width and embedding methods.