# Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | 2018 | 2019 | 2020 | newer lectures)

On 12.5.2011 at 12:20 in S1, there is the following noon lecture:

# 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

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | 2018 | 2019 | 2020 | newer lectures)

Webmaster: kamweb.mff.cuni.cz Archive page