Skip to main content
3 of 5
added a reference to [S20]
Jan Kyncl
  • 6.1k
  • 1
  • 24
  • 31

Assuming an unpublished Ramsey-type result by Robertson and Seymour about Kuratowski minors [FK18, Claim 5], which is now "folklore" in the graph-minor community, an asymptotic variant of the crossing lemma, $\operatorname{cr}(G)\ge \Omega(e^3/n^2)$, is true even for the pair crosing number on a fixed surface, such as a torus.

With Radoslav Fulek [FK18, Corollary 9] we have shown that [FK18, Claim 5] implies an approximate version of the Hanani–Tutte theorem on orientable surfaces. In particular, [FK18, Claim 5] implies that there is a constant $g$ such that for every graph $G$ that can be drawn on the torus with every pair of independent edges crossing an even number of times, $G$ can be drawn on the orientable surface of genus $g$ without crossings. This gives an upper bound $3n + O(g)$ on the number of edges of every such graph $G$, and this can be used in the probabilistic proof of the crossing lemma, as described on p. 5-6 of Marcus Schaefer's survey [S20], mentioned in Claus Dollinger's answer. See also [SSSV96, Theorem 4.1].

References:

[FK18] https://dx.doi.org/10.4230/LIPIcs.SoCG.2018.40, https://arxiv.org/abs/1803.05085 - R. Fulek and J Kynčl, The $\mathbb Z_2$-genus of Kuratowski minors

[SSSV96] https://doi.org/10.1007/BF02086611 - F. Shahrokhi, L. A. Székely, O. Sýkora and I. Vrt'o, Drawings of graphs on surfaces with few crossings, Algorithmica 16, 118-131 (1996)

[S20] https://doi.org/10.37236/2713 - M. Schaefer, The Graph Crossing Number and its Variants: A Survey, The Electronic Journal of Combinatorics, DS21: Feb 14, 2020.

Jan Kyncl
  • 6.1k
  • 1
  • 24
  • 31