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 , pp. 25-30(Official URL: http://dx.doi.org/10.1007/978-3-540-77537-9_5).

Full text not available from this repository.

Abstract

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.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-540-77537-9_5
Classifications: G Algorithms and Complexity > G.420 Crossings
URI: http://gdea.informatik.uni-koeln.de/id/eprint/825

Actions (login required)

View Item View Item