Improvement on the decay of crossing numbers

Abstract

We prove that the crossing number of a graph decays in a "continuous fashion" in the following sense. For any epsilon > 0 there is a delta > 0 such that for a sufficiently large n, every graph G with n vertices and m a parts per thousand yen n (1+epsilon) edges, has a subgraph G' of at most (1 - delta)m edges and crossing number at least (1 - epsilon)CR(G).

This generalizes the result of J. Fox and Cs.

Tóth.

Keywords

• Crossing number
• Embedding method