algorithm - 一般に NP 困難であるが、平面グラフで多項式時間解を持つ問題のリストは?

Question

グラフ問題として定式化できる多くの問題に遭遇しました。一般にNP困難ですが、グラフが平面であることが証明される場合があります。したがって、これらの問題とアルゴリズムを学ぶことに興味があります。

私が知る限り：

1. 平面グラフの最大カット
2. 平面グラフの 4 色
3. 立方平面グラフの最大独立集合

誰かがこのリストを完成させてくれることを願っています。

Answer 1

このNP 完全問題の大要では、インデックスの平面の下にかなりの数 (~25) のエントリがあります。これらのエントリは通常、平面入力が PTAS を許可する問題にリンクしています。