6
$\begingroup$

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.

3 Answers 3

5

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.

  • 0
    @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.2012-03-28
4

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

  • 1
    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.2012-01-19
0

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.