1
$\begingroup$

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?

$\endgroup$
3
  • 2
    $\begingroup$ Wouldn't zero be the upper bound on edge crossings for an embedding? $\endgroup$ Mar 23, 2013 at 0:13
  • 1
    $\begingroup$ My guess is that the question is supposed to be whether there is an upper bound on the minimum crossings in the plane. $\endgroup$ Mar 23, 2013 at 1:20
  • 3
    $\begingroup$ Please read mathoverflow.net/howtoask and revise this question. $\endgroup$ Mar 23, 2013 at 2:38

3 Answers 3

6
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I should have either said $K_7$ and $K_6$, or just $K_5$ for both. $\endgroup$ Mar 23, 2013 at 6:25
4
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ 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? $\endgroup$ Mar 24, 2013 at 20:54
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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