CompSci 269S, Winter 2008: Theory Seminar
Feb 29, 2008, 1:00pm in Bren Hall 1423
The Graph Genus Problem is NP-Complete
by Carsten Thomassen, in Journal of Algorithms 10:4 (1989)
presented by Darren Strash
Abstract:
It is NP-complete to tell, given a graph /G/ and a natural number /k/,
whether /G/ has genus /k/ or less.