Predavatelj: Drago Bokal
It is very well-known that there are precisely two minimal non-planar
graphs: K_5 and K_{3,3} (degree 2 vertices being irrelevant in this
context). In the language of crossing numbers, these are the only
1-crossing-critical graphs: they each have crossing number at least one,
and every proper subgraph has crossing number less than one. In 1987,
Kochol exhibited an infi nite family of 3-connected, simple
2-crossing-critical graphs. Recently, a complete characterization of
2-crossing-critical graphs was finalized by Richter, Salazar, Oporowski,
and Bokal. An overview of this characterization will be presented in the
talk. In particular, we will introduce the concepts and some shorter
arguments needed in the proof of the following:
graphs: K_5 and K_{3,3} (degree 2 vertices being irrelevant in this
context). In the language of crossing numbers, these are the only
1-crossing-critical graphs: they each have crossing number at least one,
and every proper subgraph has crossing number less than one. In 1987,
Kochol exhibited an infi nite family of 3-connected, simple
2-crossing-critical graphs. Recently, a complete characterization of
2-crossing-critical graphs was finalized by Richter, Salazar, Oporowski,
and Bokal. An overview of this characterization will be presented in the
talk. In particular, we will introduce the concepts and some shorter
arguments needed in the proof of the following:
Let G be a 2-crossing-critical graph.
1. Then G has minimum degree at least two and is a subdivision of a
2-crossing-critical graph with minimum degree at least three.
Moreover, suppose G has minimum degree at least three. Then:
2. if G is 3-connected, then either G has a subdivision of V_{10} and a
very particular tile structure or has at most 3 million vertices; or
3. G is not 3-connected and is one of 49 particular examples; or
4. G is 2- but not 3-connected and is obtained from a 3-connected
example by replacing digons with digonal paths.
