algorithm - 通常是 NP-hard 但在平面图中具有多项式时间解的问题列表？

Question

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

据我所知：

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

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

Answer 1

在这个NP 完全问题纲要中，在索引中的平面下有很多（~25）个条目。这些条目通常链接到平面输入允许 PTAS 的问题。