Bogdan Oporowski, Characterizing 2-crossing-critical graphs

Characterizing 2-crossing-critical graphs
Bogdan Oporowski
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: K5 and K3,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 V10; (ii) a proof that there are only finitely many 3-connected 2-crossing-critical graphs not containing a subdivision of V10; (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 V8.
This is a joint work with Drago Bokal, Bruce Richter, and Gelasio Salazar.


Comments are closed.