On the Decay of Crossing Numbers of Sparse Graphs

Jõzsef Balogh, Jesus Leaños, Gelasio Salazar

Research output: Contribution to journalArticlepeer-review

Abstract

Richter and Thomassen proved that every graph has an edge e such that the crossing number cr(G-e) of G-e is at least (2/5)cr(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 strenghthened 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 article 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.

Original languageEnglish (US)
Pages (from-to)226-251
Number of pages26
JournalJournal of Graph Theory
Volume80
Issue number3
DOIs
StatePublished - Nov 1 2015

Keywords

  • crossing numbers
  • decay of crossing numbers
  • expected crossing numbers
  • light subgraphs

ASJC Scopus subject areas

  • Geometry and Topology

Fingerprint Dive into the research topics of 'On the Decay of Crossing Numbers of Sparse Graphs'. Together they form a unique fingerprint.

Cite this