Is the crossing number of a non-planar graph a function of the surface in which it is embeddable?

I know that a non-planar graph with one crossing can be embedded in a torus, and I expected that a graph with two crossings would require a double torus. This does not seem to be the case (cf. the Petersen graph), and I am wondering what the relationship is between the crossing number of the graph and the genus of the surface.

Ultimately, I am looking for a way to guide my students to see that the Euler characteristic of a connected graph (when embedded in the simplest suitable surface) is dependent upon the genus of that surface. In other words, that the Euler characteristic tells us more about the surface than about the graph.

-

In general, what we only know to be true is that the genus $g(G)$ of a graph $G$ is less than or equal to the plane crossing number $cr(G)$ of $G$, i.e. $$g(G)\leq cr(G).$$ To prove it, suppose that you have a drawing of $G$ on the plane with $cr(G)$ crossings. Then add a handle at each crossings, you can a drawing of $G$ without crossing on the surfaces with $cr(G)$ handles.

In fact, one can construct example such that $cr(G)-g(G)$ is arbitrarily large. For example, the crossing number of $C_3\times C_n$ is given by $cr(C_3\times C_n)=n$ (see here), but $g(C_3\times C_n)=1$ (Can you draw $C_3\times C_n$ on the torus without any crossings?). In fact, for $m\geq n$, we have $g(C_m\times C_n)=1$, and it is conjectured that $$cr(C_m\times C_n)=(m-2)n,$$ which is known for $m\leq 6$ (See here.) Therefore, there are many examples showing that $cr(G)-g(G)$ can be arbitrarily large.

-
I don't see how $g(C_3\times C_n)=1$ is consistent with $m\ge n$ implying $g(C_m\times C_n)=0$. – Gerry Myerson Mar 28 '12 at 12:16
@GerryMyerson: Oh yes, that's a typo. What I wanted to say is that $g(C_m\times C_n)=1$. Thanks for pointing it out. – Paul Mar 28 '12 at 13:16

Data point: the crossing number of the complete graph on $n$ vertices goes up as $n^4$, while the genus only goes up as $n^2$.

-
Can you say more about this? It seems to me that for the complete graphs on n=1, 2, 3, 4 the crossing number does not change. But for n=5 the crossing is 1 and for n=6 the crossing number is 3(?). – Jacob Nazeck Jan 19 '12 at 22:10
Do not be misled by small values of $n$. See garden.irmacs.sfu.ca/?q=op/… for more information on the crossing number of the complete graph. – Gerry Myerson Jan 19 '12 at 22:18
Thanks! I can't tell you how excited my students are to know that they are investigating an open question in mathematics. Many of them assumed that the only unsolved problems left are ones they wouldn't be able to understand. – Jacob Nazeck Jan 19 '12 at 23:35

I just recently read this paper on "Topological effects in graphene". There on page 9 it is shown how the honeycomb structure of graphene might be distorted with pentagons and/or heptagons, to get structures like spheres a.k.a. fullerenes, (nano)tubes or tori.

-