c++ - グラフの平面性

Question

私はグラフ ライブラリを実装しており、いくつかの基本的なグラフ アルゴリズムをそれに含めたいと考えています。平面グラフについて読んだことがあり、グラフが平面かどうかをチェックする関数をライブラリに含めることにしました。Web で多くの効率的なアルゴリズムを見つけましたが、それらにはすべて同じ欠点がありました。それらを実装するのは非常に困難です。これが私の質問です。理解しやすく、実装しやすい平面性チェックのアルゴリズムは存在しますか?

注： C++で書いています

Answer 1

これは数学の質問ですが、とにかく私の記憶の深さとウィキペディアから

有限グラフは、K5 (5 つの頂点の完全なグラフ) または K3,3 (6 つの頂点の完全な 2 部グラフで、そのうちの 3 つが互いに接続されている) のサブディビジョンであるサブグラフを含まない場合にのみ平面です。三）。