Improvement on the Decay of Crossing NumbersCerný, 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 2426, 2007 , pp. 2530(Official URL: http://dx.doi.org/10.1007/9783540775379_5). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783540775379_5
AbstractWe 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 (1delta)m edges and crossing number at least (1varepsilon)cro(G). This generalizes the result of J. Fox and Cs. Tóth.
Actions (login required)
