Search code examples
algorithmgraphnp-completenp-hardplanar-graph

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:

  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.

Solution

  • 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.