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