"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?

Answer summary:

• There are 103 forbidden subgraphs for the Möbius strip that are explicitly known and drawn on page 212ff of Dan Archdeacon's thesis.
• There are 35 forbidden minors for the Möbius strip, they are explicitly known, and even better there are only 6 cubic forbidden minors, each with an intuitive explanation.

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

Solution 1:

Here is the answer by Jim Belk:

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

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.

Solution 2:

As anon notes in a comment, for this question the Möbius strip is the same as the projective plane. No doubt you are familiar with the Kuratowski theorem for embedding on a sphere. For each surface, there is an analogous theorem, that is, a finite list of minimal non-embeddable graphs. It has been found that these lists, while finite, are much larger for other surfaces than they are for the sphere, and only a very few of these lists have actually been found. I think the projective plane may be one of the ones for which the list is known, but large, so large that using it to determine embedability is not easy (at least, not by hand).

I'm aware that there are efficient planarity algorithms that don't rely (directly) on Kuratowski. I don't know whether there are similar algorithms for the projective plane (or other surfaces).

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