平面图中一般NP困难但具有多项式时间解的问题列表

Question

我遇到了许多可以公式化为图问题的问题。它通常是NP难的，但有时图可以被证明是平面的。因此，我对学习这些问题和算法很感兴趣。

据我所知：

1. 平面图中的最大割
2. 平面图的四着色
3. 三次平面图中的最大独立集

希望有人能完成这份清单。

Answer 1

在这个NP完全问题简编中，在索引中的平面下有大量（~25）个条目。这些条目通常与平面输入允许PTAS的问题有关。