一般的にNP-hardであるが、平面グラフで多項式時間解を持つ問題のリスト？

Question

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

私が知っている限りでは：

平面グラフ
1. フォー着色立方平面グラフの平面グラフ
2. 最大独立集合に

ホープ誰かで

最大カットこのリストを完成することができます。 NP完全問題のこのcompendiumで

Answer 1

、indexで平面下のエントリの良い数（〜25）があります。これらのエントリは通常、プレーナ入力がPTASを許可する問題にリンクします。