Skip to main content
2 of 5
Name of paper
LSpice
  • 12.9k
  • 4
  • 45
  • 69

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. 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)

Jan Kyncl
  • 6.1k
  • 1
  • 24
  • 31