logoalt Hacker News

emil-lplast Thursday at 10:41 AM0 repliesview on HN

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.