Список проблем, которые в целом являются NP-трудными, но есть ли решение за полиномиальное время в плоских графах?

Я столкнулся со многими проблемами, которые можно сформулировать как проблему графа. В целом это NP-сложно, но иногда можно доказать, что граф плоский. Следовательно, я заинтересован в изучении этих задач и алгоритмов.

Насколько я знаю:

1. Максимальное разрезание в планарных графах
2. Раскраска в четыре цвета в планарных графах
3. Максимально независимое множество в кубической планарные графы

Надеюсь, кто-нибудь сможет дополнить этот список.