Halin's Theorem characterizes those locally finite infinite graphs that embed in the plane without accumulation points by giving a set of six topologically-excluded subgraphs. We prove the analogous theorem for graphs that embed in an open M"obius strip without accumulation points. There are 153 such obstructions under the ray ordering defined herein. There are 350 obstructions under the minor ordering. There are 1225 obstructions under the topological ordering. The relationship between these graphs and the obstructions to embedding in the projective plane is similar to the relationship between Halin's graphs and ${ K_5 , K_{3,3} }$. |
Keywords
Infinite graphs, graph embeddings, accumulation points
Math Review Classification
Primary 05C10
Last Updated
Length
12
Availability
This article is available in: