List of problems that are in general NP-hard but have polynomial-time solution in planar graphs?
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:
- Max cut in planar graphs
- Four-coloring in planar graphs
- Max Independent Set in cubic planar graphs
Hope someone can complete this list.