Characterizing 2-crossing-critical graphs

Bogdan Oporowski

Department of Mathematics, Louisiana State University, Baton Rouge, LA , USA

Department of Mathematics, Louisiana State University, Baton Rouge, LA , USA

2015/11/18 Wed 5PM-6PM

The celebrated theorem of Kuratowski characterizes those graphs that require at least one crossing when drawn in the plane, by exhibiting the complete list of topologically-minimal such graphs. As it is very well known, this list contains precisely two such 1-crossing-critical graphs: K

This is a joint work with Drago Bokal, Bruce Richter, and Gelasio Salazar.

_{5}and K_{3,3}. The analogous problem of producing the complete list of 2-crossing-critical graphs is significantly harder. In fact, in 1987, Kochol exhibited an infinite family of 3-connected 2-crossing-critical graphs. In the talk, I will discuss the current status of the problem, including our recent work, which includes: (i) a description of all 3-connected 2-crossing-critical graphs that contain a subdivision of the Möbius Ladder V_{10}; (ii) a proof that there are only finitely many 3-connected 2-crossing-critical graphs not containing a subdivision of V_{10}; (iii) a description of all 2-crossing-critical graphs that are not 3-connected; and (iv) a recipe on how to construct all 3-connected 2-crossing-critical graphs that do not contain a subdivision of V_{8}.This is a joint work with Drago Bokal, Bruce Richter, and Gelasio Salazar.