On the Decay of Crossing Numbers

Fox, Jacob and Tóth, Csaba D. (2007) On the Decay of Crossing Numbers. In: Graph Drawing 14th International Symposium, GD 2006, September 18-20, 2006 , pp. 174-183(Official URL: http://dx.doi.org/10.1007/978-3-540-70904-6_18).

Full text not available from this repository.

Abstract

The crossing number \cn(G) of a graph G is the minimum number of crossings over all drawings of G in the plane. In 1993, Richter and Thomassen [13] conjectured that there is a constant c such that every graph G with crossing number k has an edge e such that \cn(G-e) \geq k-c\sqrt{k}. They showed only that G always has an edge e with \cn(G-e) \geq \frac{2}{5}\cn(G)-O(1). We prove that for every fixed \epsilon>0, there is a constant n_0 depending on \epsilon such that if G is a graph with n>n_0 vertices and m>n^{1+\epsilon} edges, then G has a subgraph G' with at most (1-\frac{1}{24\epsilon})m edges such that \cn(G') \geq (\frac{1}{28}-o(1))\cn(G).

Item Type: Conference Paper 10.1007/978-3-540-70904-6_18 G Algorithms and Complexity > G.420 CrossingsZ Theory > Z.999 Others http://gdea.informatik.uni-koeln.de/id/eprint/772