“Planar” graphs on Möbius strips

Is there an easy way to tell if a graph can be embedded on a Möbius strip (with no edges crossing)?

A specific version of this: if a simple graph with an odd number of vertices has all vertices of degree 4, can it be embedded on a Möbius strip?

I have not yet answered the second question, but Jim Belk's excellent explanation has given me good ideas.

-
From Wikipedia: "The non-orientable genus of a graph is the minimal integer n such that the graph can be drawn without crossing itself on a sphere with n cross-caps (i.e. a non-orientable surface of (non-orientable) genus n). (This number is also called the Euler genus and the demigenus.)" It is also equivalent to being embeddable in the real projective plane $\mathbb{RP}^2$. –  anon Oct 25 '11 at 20:56
@anon: How do you calculate it? –  Jack Schmidt Oct 25 '11 at 20:57
The Robertson–Seymour theorem implies there must be a suitable finite set of forbidden minors. But at en.wikipedia.org/wiki/Forbidden_minor there is a list that doesn't include the Möbius band or the projective plane. –  Michael Hardy Oct 25 '11 at 22:20
If i read it properly, example 3 (the solution is included) in this paper provides the answer to your last question: web.science.mq.edu.au/~chris/topology/chap05.pdf –  N. S. Oct 27 '11 at 19:58
@user9176: K44 would have 13 faces on the Möbius strip, but only 16 edges and a girth of 4. So if I look at all the boundaries of the faces, that is at least 4*13 edges, each counted twice, but that is much bigger than 2*16. So yes, K44 is completely wrong for the Möbius strip. If you want I can make a separate question for the "4" thing. For this one I'd have to accept Michael Hardy's answer, and as the question is stale you won't get enough votes here. –  Jack Schmidt Oct 27 '11 at 21:39

Here is the answer, by Jim Belk: http://cornellmath.wordpress.com/2007/07/04/graph-minor-theory-part-3

QUOTE:

There are 35 different forbidden minors for the projective plane, and these have been computed explicitly. (See Mohar and Thomassen, pg. 198 for the complete list.)

END OF QUOTE.

Here's the book that lists the 35 forbidden minors: www.amazon.com/Surfaces-Hopkins-Studies-Mathematical-Sciences/dp/0801866898

This is for a projective plane. If a graph can be embedded in the projective plane, then just puncture a hole in the plane at some point you're not using for the embedding, and you've got an embedding in the Möbius band. And if it can be embedded in the Möbius band, then it can be embedded in the projective plane since the Möbius band is a subset of the projective plane.

In a sense maybe this doesn't fully answer the question. For planarity, it is necessary that the Euler characteristic be 2. Is that also sufficient? If so, you'd have a criterion that doesn't explicitly mention how many forbidden minors there are, or which graphs those are.

-
Belk adds: "The torus seems to have hundreds of forbidden minors, and the complete list is not yet known." –  Michael Hardy Oct 25 '11 at 22:58
And just for my sanity, note how this is different from the 103 mentioned by Gerry: these are forbidden minors where one has a little more flexibility in deriving graphs from the original graph. –  Jack Schmidt Oct 26 '11 at 0:09
Here are the 35 forbidden minor graphs: emba.uvm.edu/~archdeac/graphs/projective.ps –  Jack Schmidt Oct 26 '11 at 0:16
EDIT: I found a reference to a list of 103 graphs that do for the Möbius strip (equivalently, projective plane) what $K_5$ and $K_{3,3}$ do for the plane (equivalently, sphere).