ICS Theory Group

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.