Working Seminar on Formal Models, Discrete Structures, and Algorithms

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

Luke Postle (School of Mathematics, Georgia Tech)

When: Wednesday, May 18, 2pm

Where: room G2.91b


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 find the set of all 3-connected minor minimal non-projective planar graphs with an internal 3-separation.

This is joint work with Arash Asadi and Robin Thomas