KAIST Discrete Math Seminar

In this talk, we define nearly planar graphs, that is, graphs that are edgeless or have an edge whose deletion results in a planar graph. We show that all but finitely many graphs that are not nearly planar and do not contain one particular graph have a well-understood structure based on large Mobius ladders. D. Archdeacon and C. Bonnington proved that a cubic obstruction for near-planarity is the same as an obstruction for embedding on the spindle surface and they gave the topological obstruction set for cubic nearly planar graphs. Now, we are searching graph minor obstructions for embedding on the spindle surface. This is a joint work with Bogdan Oporowski and Guoli Ding.