13
$\begingroup$

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:

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

  • 0
    @user9176: thanks! this is making the "irreducible" list make a lot more sense.2011-10-29

2 Answers 2

7

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.

  • 0
    Here are the 35 forbidden minor graphs: http://www.emba.uvm.edu/~archdeac/graphs/projective.ps2011-10-26
5

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

  • 2
    Yes. It's curious that for the plane, Kuratowski and forbidden minors give the same two graphs, but for other surfaces the two approaches give different lists.2011-10-26