McGill University - School of Computer Science

Algorithms Seminar 2002

Everybody is welcome!

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.

Direct questions, comments, additions to and removals from the mailing list, and suggestions for speakers to us at beezer(at) , or .
Web Address: