
> 
> **QUICK FINAL UPDATE**: Just wanted to thank you MO users for all your support. Special thanks for the fast answers, I've accepted first one, appreciated the clarity it gave me. I've updated my torus algorithm with ${\rm cr}(G)$. Works fine on my full test set, i.e. evidence for ${\rm cr}(G)={\rm pcr}(G)$ on torus. More on this later, will test sharper bound from last answer as well. **I'm going to submit in time!** Thanks again MO users for all your help!
> 
> 
> 


Original post:  

I apologize if „crisis“ is too strong a word, but I am in a mode of panic, if that's the right word: In two weeks, I should be submitting my Ph.D. Thesis, but I have just received bad news, or I should say information that makes me very concerned. It is really an emergency situation:


My thesis is in computer science, algorithms related to graph drawings on the sphere and the torus. One of the cornerstone mathematical results I am relying on is the graph edge crossing lemma (or edge crossing inequality). It gives a lower bound for the minimum number of edge crossings ${\rm cr}(G)$ for any drawing of the graph $G$ with $n$ vertices and $e$ edges
$${\rm cr}(G)\geq \frac{e^3}{64n^2}$$
for $e>4n$.



> 
> **PROBLEM:** I am reading in the article of Pach and Tóth that there is a possibility that mathematics papers on crossing numbers operate with different definitions. There is the crossing number ${\rm cr}(G)$ (minimum of edge crossings in a drawing of $G$), but also the *pair crossing number*
> ${\rm pcr}(G)$, the minimum number of edge pairs crossing in a drawing of $G$.
> *I double-checked my algorithms and, based on this definition, I clearly apply the pair crossing number ${\rm pcr}(G)$*
> 
> 
> 



> 
> **CRITICAL QUESTION:** Can you confirm to me that the edge crossing lemma remains valid on the sphere and the torus also for the pair crossing number ${\rm pcr}(G)$?
> 
> 
> 


Reference: János Pach and Géza Tóth. [Which crossing number is it anyway?](https://doi.org/10.1006/jctb.2000.1978) J. Combin. Theory Ser. B, 80(2): 225–246, 2000.


And Wikipedia article as a starting point <https://en.wikipedia.org/wiki/Crossing_number_inequality>



Issue UPDATE: in graph theory, different definitions of edge crossing numbers - impact on applications?
$\DeclareMathOperator\cr{cr}\DeclareMathOperator\pcr{pcr}$For the pair crossing number $\pcr(G)$, the short answer is **yes** the crossing lemma holds for drawings on the sphere, but it is **not known** whether it also holds on the torus.


The best and most current reference for you could be the survey article from Schaefer, updated in February 2020: “The Graph Crossing Number and its Variants: A Survey” from the Electronic Journal of Combinatorics
(<https://doi.org/10.37236/2713>).


The relevant pages for you are pages 5 and 6 with the following quote from Schaefer:



> 
> “Since the Hanani–Tutte theorem is not known to be true for the torus, this means that we do not currently have a proof of the crossing lemma for $\pcr$ or $\pcr\_−$ on the torus.”
> 
> 
> 


Generally, $\pcr(G)\leq \cr(G)$. It is still an open problem whether they are equal or not. The first proofs of the crossing lemma did not make the distinction. The first one to raise the ambiguity was Mohar (1995) in a conference talk.


The [Pach and Tóth](https://doi.org/10.1006/jctb.2000.1978) (2000) paper that you mention does make the distinction between $\pcr(G)$ and $\cr(G)$, and applies Hanani–Tutte in the proof of the crossing lemma, which ensures that it also holds for $\pcr(G)$.


The issue is that you can apply Hanani–Tutte for the sphere (and the projective plane), but you cannot apply it for the torus. For surfaces of genus $\geq4$ it is known to be false, see Fulek and Kynčl (2019). This means the torus is really “in-between”.


**Edit:** Adding the references


Bojan Mohar (1995): Problem mentioned at the special session on Topological Graph Theory, Mathfest, Burlington, Vermont. (cited from: L.A. Székely (2016): [Turán’s Brick Factory Problem: The Status of the Conjectures of Zarankiewicz and Hill](https://doi.org/10.1007/978-3-319-31940-7_13). In: R. Gera et al. (eds.)(2016): Graph Theory—favorite conjectures and open problems. 1.)


Hanani–Tutte Theorem <https://en.wikipedia.org/wiki/Hanani%E2%80%93Tutte_theorem>


Radoslav Fulek and Jan Kynčl (2019): [Counterexample to an Extension of the Hanani–Tutte Theorem on the Surface of Genus 4](https://doi.org/10.1007/s00493-019-3905-7). Combinatorica, 39(6):1267–1279


