Note that the second distinction you made is actually trivial. Coloring the vertices of a planar graph is the same problem as coloring the regions of a differe

Note that the second distinction you made is actually trivial. Coloring the vertices of a planar graph is the same problem as coloring the regions of a different planar graph. The graphs are duals: http://en.wikipedia.org/wiki/Dual_graph http://en.wikipedia.org/wiki/Dual_graph In this case, the dual of a grid is a grid. So at least that part of it would be the same problem. The other distinctions are true, though.