[JohnKemeny]

SAT is NP-complete even when the variable-clause graph is planar.

Vertex cover is NP-complete on planar graphs even if each vertex has at most three neighbors.

Travelling Salesman is NP-complete on planar graphs.

So is independent set, dominating set, 3-coloring...

[yarg]

It's not the travelling salesman - as per the description it's an unweighted graph.

This reduces the problem from finding the shortest hamiltonian cycle to finding any such cycle.