Graph Theory Seminar
Thursday, March 17, 2011 - 12:05
1 hour (actually 50 minutes)
The property that a graph has an embedding in projective plane is closed under taking minors. So 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 structure of G is well understood. 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 find the set of all 3-connected minor minimal non-projective planar graphs with an internal 3-separation. This is joint work with Luke Postle and Robin Thomas.