List of problems that are in general NP-hard but have polynomial-time solution in planar graphs?

Question

I encountered many problems that can be formulated as graph problem. It is in general NP-hard but sometimes the graph can be proved to be planar. Hence, I am interested in learning these problems and the algorithms.

So far as I know:

1. Max cut in planar graphs
2. Four-coloring in planar graphs
3. Max Independent Set in cubic planar graphs

Hope someone can complete this list.

Slangy

I think this belongs to cstheory.se – Abacist

Looking at their FAQ, I think cstheory.se would probably close this. – Satyriasis

I had closed this because it seems like a "List of X" question, but I'm reopening in hopes that there's one resource with the answer. If others feel there's no one right answer they can vote to close. – Satyriasis

Answer 1

In this compendium of NP-complete problems, under planar in the index there are a good number (~25) of entries. These entries typically link to problems where planar input admits a PTAS.

Loyola