一般NP-hard但在平面图中有多项式时间解的问题列表？

Question

我遇到了许多可以表示为图形问题的问题.它通常是NP难的,但有时可以证明图是平面的.因此,我有兴趣学习这些问题和算法.

据我所知:

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

希望有人可以填写此列表.

Answer 1

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