0
Graphvizでsmall planar graphを描きましたが、1つの場所に2つのエッジの交点があります。私はすべての平面グラフが交差点なしで描かれるわけではないということを読みました。なぜなら、それはNP困難な問題であるからです。また、Graphvizには複雑なアルゴリズムを実装していないこともあります。しかし、その交差点は可能な限り簡単に修正できるので、おそらくそれを取り除く方法があります。ここでGraphvizで小さな平面グラフを描く
は、私が使用したオプションは次のとおりです。
overlap = false;
splines = curved;
nodesep = 0.5;
そして、ここではグラフです： 
だから、なしで、1つの交差点（7-18と25-38）を固定する方法があります私が行ったようにエッジの順序を変更するhere？少なくともO(n^2)のような2つの頂点を交換し、交差点が消滅したかどうかを確認するアルゴリズムはありませんか？
'O（N） 'アルゴリズム[1]（https://archive.org/details/PlanarityTestingByPathAddition）[2]（HTTPS：// dl.acm.org/citation.cfm?id=321852）]を使用して平面性をテストし、プレーンな埋め込みを作成します。エッジ横断のない平面グラフの埋め込みを作成することは可能です（これは平面グラフの定義なので）。これはNP困難な問題ではなく、間違っているという回答がある場合です。つまり、私はGraphVisを一度も使用していないので、そのプログラムでそれを解決するのを手助けすることはできません。 – MT0
@ MT0私は速い平面のグラフチェックがあることを知っています。私は平面グラフを描くことがNPHであることを意味しました。しかし、私は間違っていた。私はチェックして、実際には（最小限のエッジ交差を持つグラフを描画するのはNPHです）（https://stackoverflow.com/a/2348551/2377652）私の悪い。 – user1
最小限のエッジクロッシングを持つ非平面グラフを描くのは難しい - エッジクロッシングのない平面グラフを描くことは、線形時間（ 'O（N）'）で解決された問題です。 1つの方法です。 – MT0