Physical Sciences and Mathematics Commons^™

Projective-Planar Graphs With No K3,4-Minor. Ii., John Maharry, Dan Slilaty

Mathematics and Statistics Faculty Publications

The authors previously published an iterative process to generate a class of projectiveplanar K3,4-free graphs called ‘patch graphs’. They also showed that any simple, almost 4-connected, nonplanar, and projective-planar graph that is K3,4-free is a subgraph of a patch graph. In this paper, we describe a simpler and more natural class of cubic K3,4- free projective-planar graphs which we call M¨obius hyperladders. Furthermore, every simple, almost 4-connected, nonplanar, and projective-planar graph that is K3,4-free is a minor of a M¨obius hyperladder. As applications of these structures we determine the page number of patch graphs and of M¨obius hyperladders.