On the decay of crossing numbers of sparse graphs

Details On the decay of crossing numbers of sparse graphs On the decay of crossing numbers of sparse graphs

2012-03-02

arxiv.org/abs/1203.0510v1

Mathematics

Combinatorics

Scientific paper

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\'oth 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 \v{C}ern\'{y}, Kyn\v{c}l and G. T\'oth. 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.

Affiliated with

Also associated with

No associations

Rating

On the decay of crossing numbers of sparse graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the decay of crossing numbers of sparse graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the decay of crossing numbers of sparse graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-167039