Halin's Theorem for the M"obius Strip

Dan Archdeacon, C. Paul Bonnington, Marisa Debowsky and Michael Prestidge


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} }$.

Infinite graphs, graph embeddings, accumulation points

Math Review Classification
Primary 05C10

Last Updated


This article is available in: