Structure of crossing-critical graphs

Graph Theory Seminar
Friday, September 23, 2011 - 15:05
1 hour (actually 50 minutes)
Skiles 005
Charles University, Prague, Czech Republic
A graph G is k-crossing-critical if it cannot be drawn in plane with fewer than k crossings, but every proper subgraph of G has such a drawing. We aim to describe the structure of crossing-critical graphs. In this talk, we review some of their known properties and combine them to obtain new information regarding e.g. large faces in the optimal drawings of crossing-critical graphs. Based on joint work with P. Hlineny and L. Postle.