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?
$\begingroup$
$\endgroup$
3
-
2$\begingroup$ Wouldn't zero be the upper bound on edge crossings for an embedding? $\endgroup$– Ryan BudneyCommented 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$– Douglas ZareCommented Mar 23, 2013 at 1:20
-
3$\begingroup$ Please read mathoverflow.net/howtoask and revise this question. $\endgroup$– Theo Johnson-FreydCommented Mar 23, 2013 at 2:38
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
1
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.
answered Mar 23, 2013 at 4:23
-
$\begingroup$ I should have either said $K_7$ and $K_6$, or just $K_5$ for both. $\endgroup$ Commented Mar 23, 2013 at 6:25
$\begingroup$
$\endgroup$
1
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$.
-
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$ Commented Mar 24, 2013 at 20:54
$\begingroup$
$\endgroup$
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.
