Improvement on the Decay of Crossing Numbers
Cerný, Jakub and Kynčl, Jan and Tóth, Géza (2008) Improvement on the Decay of Crossing Numbers. In: Graph Drawing 15th International Symposium, GD 2007, September 24-26, 2007, Sydney, Australia , pp. 25-30 (Official URL: http://dx.doi.org/10.1007/978-3-540-77537-9_5).
Full text not available from this repository.
We prove that the crossing number of a graph decays in a "continuous fashion" in the following sense. For any varepsilon>0 there is a delta>0 such that for n sufficiently large, every graph G with n vertices and mge n^1+varepsilon edges has a subgraph G' of at most (1-delta)m edges and crossing number at least (1-varepsilon)cro(G). This generalizes the result of J. Fox and Cs. Tóth.
Repository Staff Only: item control page