| DATE: | Wednesday November 2nd, 2002 |
| TIME: | 4:30 PM - 5:30 PM |
| PLACE: | McConnell 320 |
| TITLE: | Computing the genus of graphs in minor closed families |
| SPEAKER: | Bojan Mohar, University of Ljubljana, Slovenia |
After Thomassen proved that the genus problem is NP-complete,
Neil Robertson came out with a reserach program about genus computations
in minor closed families of graphs. The speaker will first explain this
program in the light of the Excluded Minor Theorem of Robertson and
Seymour, and next, give an overview of known results for almost all
of the most important cases, graphs of bounded tree-width, apex graphs,
and graphs on a fixed surface. A breakthrough in the latter case has been
made rently in a joint work with Lex Schrijver.