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

Question

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

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

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

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

Answer 1

В этом сборнике проблем с NP-полными, под planar в index имеется большое количество (~ 25) записей.Эти записи обычно связаны с проблемами, когда при плоском вводе допускается PTAS.