Hard Problems for higher genus graphs Planar graphs have genus zero. Graphs embeddable on a torus have genus at most 1. My question is simple :


Are there any problems that are polynomially solvable on planar graphs but NP-hard on graphs of genus one ?
More generally are there any problems that are polynomially solvable on graphs of genus g but NP-hard on graphs of genus > g ?
This is publicity of my own work, but crossing number and 1-planarity are trivially solvable in planar graphs but hard for graphs of genus one. See http://arxiv.org/abs/1203.5944