24

Math Overflow users resolve PhD thesis crisis

 4 years ago
source link: https://mathoverflow.net/questions/366765/issue-update-in-graph-theory-different-definitions-of-edge-crossing-numbers
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

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


About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK