平面化

グラフ理論の数学分野では、平面化とは、平面グラフから非平面グラフへとグラフ描画方法を拡張する手法であり、非平面グラフをより大きな平面グラフの中に埋め込むことによって実現される。 ^{[ 1 ] [ 2 ]}

平面化は、与えられたグラフの交点を含む図を求める任意の方法を用い、各交点を新しい人工頂点に置き換えることで実行できる。これにより、各交点のある辺がパスに分割される。元のグラフは、その平面化のイマージョンマイナーとして表現される。

増分平面化では、平面化プロセスは 2 つの段階に分けられます。まず、与えられたグラフ内で大きな平面部分グラフが見つかります。次に、この部分グラフの一部ではない残りのエッジが 1 つずつ追加され、平面部分グラフの埋め込みを通してルーティングされます。これらのエッジの 1 つが既に埋め込まれているエッジと交差する場合、交差する 2 つのエッジは 2 つのエッジのパスに置き換えられ、両方のパスの中央に交点を表す新しい人工頂点が配置されます。^{[ 1 ] [ 2 ]}場合によっては、平面化プロセスに 3 番目の局所最適化段階が追加され、平面化を改善するために、交差が多いエッジが削除され、再追加されます。^{[ 1 ]}

グラフ描画にインクリメンタル平面化を用いる場合、プロセスの最初のステップで可能な限り大きな平面グラフを見つけるのが最も効果的です。残念ながら、可能な限り最大のエッジ数を持つ平面部分グラフを見つけること（最大平面部分グラフ問題^{[ 3 ]}）はNP困難であり、MaxSNP困難であるため、この問題を正確に解く、または任意にうまく近似する多項式時間アルゴリズムは存在しない可能性が高いです。 ^{[ 4 ]}

n頂点連結グラフでは、最大の平面部分グラフは最大で 3 n − 6 エッジを持ち、任意の全域木はn − 1 エッジの平面部分グラフを形成します。したがって、全域木を見つけるだけで、最大平面部分グラフを 3 分の 1 の近似比で簡単に近似できます。与えられたグラフの部分グラフとして大きな部分 2-木を見つける方法に基づいて、より良い近似比 9/4 が知られています。 ^{[ 1 ] [ 4 ]}あるいは、平面部分グラフが与えられたグラフのほぼすべてのエッジを含み、増分平面化プロセスに少数のk個の非平面エッジだけを残すことが予想される場合、実行時間がグラフサイズに対して線形であるがパラメータkに対しては非多項式である固定パラメータ扱いやすいアルゴリズムを使用して問題を正確に解くことができます。^{[ 5 ]}また、実行時間に関する保証はないものの、実際には良好なパフォーマンスを発揮する分岐限定法アルゴリズムによって問題を正確に解くこともできます。 ^{[ 1 ] [ 6 ]}このパラメータkはグラフの歪度として知られています。 ^{[ 3 ] [ 7 ]}     

また、関連する問題として、与えられたグラフの最大の平面誘導部分グラフを見つける研究も行われています。これもNP困難ですが、ごく少数の頂点を除いてすべてが誘導部分グラフに属する場合は固定パラメータで扱い可能です。 ^{[ 8 ]} Edwards & Farr (2002)は、与えられたグラフの頂点数nと最大次数 Δ の関数として、最大の平面誘導部分グラフのサイズに3 n /(Δ  + 1) という厳しい上限があることを証明しました。彼らの証明は、このサイズの誘導部分グラフを見つけるための多項式時間アルゴリズムにつながります。^{[ 9 ]} 

大きな平面部分グラフが見つかると、残りのエッジを 1 つずつ考慮して、増分平面化プロセスが続行されます。その際、既に考慮されたエッジによって形成された部分グラフの平面化が維持されます。新しいエッジをこの部分グラフの平面埋め込みに追加して、交差のある図を作成し、各交点を、交差する 2 つのエッジを分割する新しい人工頂点に置き換えます。^{[ 1 ] [ 2 ]}この手順のいくつかのバージョンでは、エッジを追加する順序は任意ですが、順序をランダムな順列に選択して、同じアルゴリズムを複数回実行し、見つかった最良の平面化を返すことも可能です。^{[ 1 ]}

このプロセスの最も単純な形式では、新しいエッジが追加される間、平面化された部分グラフの平面埋め込みは変更されません。各新しいエッジが形成する交差の数を最小限に抑える方法で各新しいエッジを追加するために、現在の埋め込みの双対グラフで最短経路アルゴリズムを使用して、新しいエッジの端点同士を接続する、交差する埋め込みの面とエッジの最短シーケンスを見つけることができます。このプロセスは、エッジごとに多項式時間かかります。^{[ 2 ]}

平面化された部分グラフの埋め込みを固定することは、結果として生じる交差の数に関して必ずしも最適ではありません。実際、平面部分グラフに 1 つのエッジを追加することによって形成されるグラフが存在し、その最適な描画では交差は 2 つだけですが、部分グラフの平面埋め込みを固定すると、線形数の交差が生成されます。^{[ 1 ]}平面部分グラフに 1 つのエッジを追加した最適な平面化を見つけることと、固定された埋め込みを維持することの間の妥協として、平面化された部分グラフのすべての埋め込みを探索し、新しいエッジによって形成される交差の数を最小化する埋め込みを見つけることができます。^{[ 1 ] [ 10 ]}