3-Connected Minor-Minimal Non-Projective Planar Graphs with an Internal 3-Separation

Luke Postle

Georgia Tech

Abstract

The property that a graph has an embedding in projective plane is closed under taking minors. By the well known theorem of Robertson and Seymour, there exists a finite list of minor-minimal graphs, call it L, such that a given graph G is projective planar if and only if G does not contain any graph isomorphic to a member of L as a minor. Glover, Huneke and Wang found 35 graphs in L, and Archdeacon proved that those are all the members of L. In this talk we show a new strategy for finding the list L.

Our approach is based on conditioning on the connectivity of a member of L. Assume G is a member of L. If G is not 3-connected then the G is a 0-,1-, or 2-sum of Kuratowski graphs (K_5 and K_{3,3}). In the case that G is 3-connected, the problem breaks down into two main cases, either G has an internal separation of order three or G is internally 4-connected. In this talk, we