[emil-lp]

I agree, that is a good point. Although it is (induced) subgraphs of 2D grids, which gets you a bit closer to the planar case (albeit with bounded degree).

It might be polytime on planar graphs, but that would be surprising.