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

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?

-
Wouldn't zero be the upper bound on edge crossings for an embedding? –  Ryan Budney Mar 23 '13 at 0:13
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

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.

-
I should have either said $K_7$ and $K_6$, or just $K_5$ for both. –  Douglas Zare Mar 23 '13 at 6:25

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

-
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

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.

-