Can all connected graphs be embedded on a closed, compact 2-Manifold?

Question

I know that there are spherical (planar) graphs such as $K_4$,and toroidal graphs such as $k_7$, but I was wondering if given any connected graph $G$, there exists a closed, compact 2-Manifold $M$ such that $G$ can be embedded in $M$? If so, does the smallest possible genus of $M$ or whether or not $M$ is orientable tell us any properties of $G$?

Answer 1

For finite graphs, the answer is yes. (For infinite graphs, your embedding of the vertex set on a compact surface will necessarily have accumulation points, which is a bit of a mess.)

To see this, just draw the graph in the sphere, such that only two edges ever cross at a single point. By compactness, we can do this by just wiggling the edges a bit to prevent triple crossings. For each crossing, add a handle for one of the crossing edges to make a 'bridge' for the one edge to go over the other (in the diagram, the added handle, viewed from above, is in blue).

Note that this construction does not give the lowest genus surface possible for an embedding, it's just an easy argument to show such a surface exists.

The minimum genus is a useful piece of information. For each genus, there is a finite set of forbidden minor obstructions, per the Robertson-Seymour Theorem (much like $K_{3,3}$ and $K_5$ are obstructions for embedding on the plane or sphere). The genus also bounds the chromatic number of the graph (so an analog of the four-colour theorem holds for any compact surface). It is also sometimes possible to create more efficient algorithms for graphs of bounded genus than for arbitrary graphs.

I don't know anything regarding orientability however.