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 thepair 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? 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

11more comments