New Bounds on Crossing Numbers

J. Pach, J. Spencer, G. Tóth

Research output: Contribution to journalArticlepeer-review

Abstract

The crossing number, cr(G), of a graph G is the least number of crossing points in any drawing of G in the plane. Denote by κ(n, e) the minimum of cr(G) taken over all graphs with n vertices and at least e edges. We prove a conjecture of Erdos and Guy by showing that κ(n, e)n2/e3 tends to a positive constant as n → ∞ and n ≪ e ≪ n2. Similar results hold for graph drawings on any other surface of fixed genus. We prove better bounds for graphs satisfying some monotone properties. In particular, we show that if G is a graph with n vertices and e ≥ 4n edges, which does not contain a cycle of length four (resp. six), then its crossing number is at least ce4/n3 (resp. ce5/n4), where c > 0 is a suitable constant. These results cannot be improved, apart from the value of the constant. This settles a question of Simonovits.

Original languageEnglish (US)
Pages (from-to)623-644
Number of pages22
JournalDiscrete and Computational Geometry
Volume24
Issue number4
DOIs
StatePublished - Dec 2000

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'New Bounds on Crossing Numbers'. Together they form a unique fingerprint.

Cite this