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 ?
Hard Problems for higher genus graphs
cc.complexity theory;ds.algorithms;graph theory;planar graphs