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.

  • 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$.2011-10-25
  • 1
    @anon: How do you calculate it?2011-10-25
  • 0
    Maybe this will help: http://web.science.mq.edu.au/~chris/topology/chap05.pdf2011-10-25
  • 1
    The [Robertson–Seymour theorem](http://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theorem) implies there must be a suitable finite set of forbidden minors. But at http://en.wikipedia.org/wiki/Forbidden_minor there is a list that doesn't include the Möbius band or the projective plane.2011-10-25
  • 0
    The notes by my colleague, Chris Cooper, that anon links, will give a necessary-but-not-sufficient condition for a graph to be embedded in a Mobius strip (equivalently, projective plane).2011-10-25
  • 0
    @GerryMyerson: yup, and I think in my case the condition is inconclusive. I do like it because it is simple.2011-10-26
  • 1
    If i read it properly, example 3 (the solution is included) in this paper provides the answer to your last question: http://web.science.mq.edu.au/~chris/topology/chap05.pdf2011-10-27
  • 0
    @user9176: so it does, but negatively :~( Thanks!2011-10-27
  • 0
    Yep, but I think that a negative answer should had been expected. The way we prove that $K_{33}$ is planar is by showing it has one more "crossing" than we can have. On the tsrip you can eliminate one (I think) of the crossing, or maybe two. But then the same Euler formula +4-cycles argument seems to imply that $K_{44}$ is not planar on the Mobius strip.2011-10-27
  • 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.2011-10-27
  • 0
    Since $4*13$ is much bigger tha $2*16$, it means that if you erase one edge from $K_{44}$ your argument should still work. Since $K_{44}\backslash e$ does't work, you can add any other graoh you want, and connected it to $K_{44}\backslash e$ by two edges to the vertices in $K_{44}\backslash e$ of degree 3. This should allow you to construct a counterexample even for odd degree.2011-10-28
  • 0
    More exactly pick $K_{44}-e$ and $K_5-f$, where the edges removed are random. Now connect one end vertex of $e$ with one end vertex of $f$ and the other to the other. You get a nice graph, which has $K_{44}-e$ as a subgraph, so shouldn't be embedable... And keep in mind that you can replace $K_5$ by many other graphs, this way you can generate lots of graphs with this property...2011-10-28
  • 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
    Belk adds: "The torus seems to have hundreds of forbidden minors, and the complete list is not yet known."2011-10-25
  • 0
    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.2011-10-26
  • 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).

  • 0
    Thanks. So this might mean there are not as many nice ways to check.2011-10-25
  • 0
    Thanks, so this one is for subgraphs that have a subdivision isomorphic to one of these 103 (in other words, Kuratowski).2011-10-26
  • 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