Halin's theorem for the Mobius strip

Dan Archdeacon, Craig Paul Bonnington, Marisa Debowsky, Michael Prestidge

Research output: Contribution to journalArticleResearchpeer-review


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 Mobius 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 K5, K3,3 .
Original languageEnglish
Pages (from-to)243 - 256
Number of pages14
JournalArs Combinatoria
Issue number1
Publication statusPublished - 2003
Externally publishedYes

Cite this