On the decay of crossing numbers of sparse graphs

2012/03/02 by Balogh, Jozsef, Leanos, Jesus, Salazar, Gelasio
#05C07 #05C10 #05C38 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1203.0510

Abstract

Richter and Thomassen proved that every graph has an edge e such that the crossing number \ucr(G-e) of G-e is at least (2/5)\ucr(G) - O(1). Fox and Cs. Tóth proved that dense graphs have large sets of edges (proportional in the total number of edges) whose removal leaves a graph with crossing number proportional to the crossing number of the original graph; this result was later strenghtened by Černý, Kynčl and G. Tóth. These results make our understanding of the decay of crossing numbers in dense graphs essentially complete. In this paper we prove a similar result for large sparse graphs in which the number of edges is not artificially inflated by operations such as edge subdivisions. We also discuss the connection between the decay of crossing numbers and expected crossing numbers, a concept recently introduced by Mohar and Tamon.

Related

• An algorithm for estimating the crossing number of dense graphs, and continuous analogs of the crossing and rectilinear crossing numbers
• Improvement on the crossing number of crossing-critical graphs
• Crossing numbers of dense graphs on surfaces
• Generalizations of the Crossing Lemma
• A slightly better bound on the crossing number in terms of the pair-crossing number