Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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
1  
@anon: How do you calculate it? –  Jack Schmidt Oct 25 '11 at 20:57
1  
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
1  
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
1  
@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
show 8 more comments

2 Answers 2

up vote 8 down vote accepted

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.

share|improve this answer
    
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
add comment

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

share|improve this answer
    
Thanks. So this might mean there are not as many nice ways to check. –  Jack Schmidt Oct 25 '11 at 22:30
    
Thanks, so this one is for subgraphs that have a subdivision isomorphic to one of these 103 (in other words, Kuratowski). –  Jack Schmidt Oct 26 '11 at 0:08
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. –  Gerry Myerson Oct 26 '11 at 1:04
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.