Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

If a graph embeds in the torus or the projective plane is there an upper bound on the number of edge crossings it has in the plane?

share|improve this question
2  
Wouldn't zero be the upper bound on edge crossings for an embedding? –  Ryan Budney Mar 23 '13 at 0:13
1  
My guess is that the question is supposed to be whether there is an upper bound on the minimum crossings in the plane. –  Douglas Zare Mar 23 '13 at 1:20
3  
Please read mathoverflow.net/howtoask and revise this question. –  Theo Johnson-Freyd Mar 23 '13 at 2:38
add comment

3 Answers

up vote 6 down vote accepted

No, there is no upper bound. For any $n$, if you take a sufficiently fine mesh on a torus or projective plane, deleting $n$ edges will still result in a graph with a $K_7$ or $K_5$ minor, respectively.

share|improve this answer
    
I should have either said $K_7$ and $K_6$, or just $K_5$ for both. –  Douglas Zare Mar 23 '13 at 6:25
add comment

There are two ways to read this question. (I'll just ignore the projective plane part.)

Zare's reading: Suppose that a graph $G$ embeds in the torus. Is there an upper bound on the number of edge crossings of $G$ when drawn in the plane?

The answer is "no". You can draw $K_7$ in the torus and then take many parallel edges. All of these graphs embed in the torus, but there is no bound on their crossing number when drawn in the plane.

My reading: What is the largest $k$ so that any graph $G$, with at most $k$ crossings in the plane, embeds in the torus? Is there an upper bound on $k$?

The answer is "yes". Note, if $k < 2$ then $G$ embeds in the torus. However $K_8$ does not embed in the torus, and can be drawn in the plane with only $18$ crossings. So $18$ is an upper bound. I'll guess that this can be improved to $k = 2$.

share|improve this answer
1  
There is another way to read it: What is the smallest function $f$ of $n$ such that any toroidal graph on $n$ vertices can be drawn in the plane with at most $f(n)$ crossings? –  Andrew D. King Mar 24 '13 at 20:54
add comment

Regarding Andrew D. King's interpretation: Djidjev and Vrto showed that the crossing number of a graph with $n$ vertices and maximum degree $d$ embedded in a genus $g$ surface is $O(gdn)$, which improves an earlier result by Pach and Toth. This is tight up to a constant multiplicative factor.

the reference: Hristo N. Djidjev and Imrich Vrto, Planar Crossing Numbers of Graphs of Bounded Genus, Discrete & Computational Geometry, Volume 48, Issue 2 (2012), 393--415.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.