平面分離定理

グラフ理論において、平面セパレータ定理は平面グラフの等周不等式の一種であり、少数の頂点を削除することで任意の平面グラフをより小さな部分に分割できることを述べています。具体的には、n頂点グラフ ( Oは大きな O 表記法を呼び出します)から頂点を削除すると、グラフをそれぞれが最大で⁠ ⁠頂点を持つ互いに素なサブグラフに分割できます。 ${\displaystyle O({\sqrt {n}})}$${\displaystyle 2n/3}$

セパレータ定理の弱い形式、つまりセパレータに⁠ ${\displaystyle O({\sqrt {n}}\log ^{3/2}n)}$⁠頂点ではなく⁠ ${\displaystyle O({\sqrt {n}})}$⁠頂点が含まれる形式は、もともと Ungar (1951) によって証明され、セパレータのサイズに厳しい漸近的境界がある形式は、Lipton & Tarjan (1979) によって最初に証明されました。彼らの研究以来、セパレータ定理はさまざまな方法で再証明され、定理の⁠ ⁠${\displaystyle O({\sqrt {n}})}$項の定数は改良され、特定の非平面グラフのクラスに拡張されました。

セパレータ定理を繰り返し適用すると、グラフのツリー分解またはブランチ分解の形をとるセパレータ階層が生成されます。セパレータ階層は、平面グラフの効率的な分割統治アルゴリズムを考案するために使用できます。また、これらの階層での動的計画法は、これらのグラフのNP 困難な最適化問題を解くための指数時間と固定パラメータで扱いやすいアルゴリズムを考案するために使用できます。セパレータ階層は、有限要素法から生じる疎な線形方程式系を解くためのガウス消去法の効率的な変形であるネストされた解法にも使用できます。

平面グラフ以外にも、固定マイナーを除いたグラフ、最近傍グラフ、有限要素メッシュなど、他のグラフのクラスにもセパレータ定理が適用されています。グラフのクラスに対するセパレータ定理の存在は、ツリー幅と多項式展開の概念によって形式化および定量化できます。

通常述べられているように、セパレータ定理は、任意の - 頂点平面グラフにおいて、 の頂点を3 つの集合、、およびに分割し、 および のそれぞれが最大で 個の頂点を持ち、 が頂点を持ち、 に 1 つの端点を持ち、 に 1 つの端点を持つ辺が存在しないことを述べています。またはがの連結サブグラフを形成する必要はありません。は、この分割のセパレータと呼ばれます。 ${\displaystyle n}$${\displaystyle G=(V,E)}$${\displaystyle G}$${\displaystyle A}$${\displaystyle S}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$${\displaystyle 2n/3}$${\displaystyle S}$${\displaystyle O({\sqrt {n}})}$${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$ ${\displaystyle G}$${\displaystyle S}$

これと同等の定式化は、任意の- 頂点平面グラフの辺を、辺が互いに素な 2 つのサブグラフと に分割して、両方のサブグラフに少なくとも個の頂点と 個の頂点が含まれるようにできるというものです。このような分割は、分離として知られています。^[1]分離が与えられた場合、頂点集合の交差が分離子を形成し、一方のサブグラフに属し、他方のサブグラフには属さない頂点は、それぞれが最大個の頂点を持つ分​​離されたサブセットを形成します。逆に、平面分離子定理の条件を満たす 、、および の 3 つのセットへの分割が与えられた場合、 に端点を持つ辺が に属し、 に端点を持つ辺が に属し、残りの辺 ( の両方の端点を持つ) が任意に分割されるような分離を形成できます。 ${\displaystyle n}$${\displaystyle G}$${\displaystyle G_{1}}$${\displaystyle G_{2}}$${\displaystyle n/3}$${\displaystyle O({\sqrt {n}})}$${\displaystyle 2n/3}$${\displaystyle A}$${\displaystyle S}$${\displaystyle B}$${\displaystyle A}$${\displaystyle G_{1}}$${\displaystyle B}$${\displaystyle G_{2}}$${\displaystyle S}$

分離定理の記述における定数は任意であり、定理の形式を変えずに開区間内の他の数値に置き換えることができる。不均等な分割で大きな集合を繰り返し分割し、結果として得られる連結成分を再グループ化することで、不均等な分割からより均等な部分集合への分割を得ることができる。^[2]${\displaystyle 2/3}$ ${\displaystyle (1/2,1)}$

行と列を持つグリッドグラフを考えてみましょう。頂点の数は です。たとえば、図では、、、およびです。が奇数の場合、中央の行は 1 つで、そうでない場合は中央に等しく近い行が 2 つあります。同様に、 が奇数の場合、中央の列は 1 つで、そうでない場合は中央に等しく近い列が 2 つあります。これらの中央の行または列のいずれかを選択してグラフから を削除すると、グラフは と の 2 つの小さな連結されたサブグラフに分割され、各サブグラフは最大で の頂点を持ちます。 の場合(図のように)、中央の列を選択すると、頂点を持つセパレータが作成され、同様に の場合、中央の行を選択すると、最大で の頂点を持つセパレータが作成されます。したがって、すべてのグリッドグラフには最大で のサイズのセパレータがあり、これを削除すると、最大で のサイズの 2 つの連結されたコンポーネントに分割されます。^[3]${\displaystyle r}$${\displaystyle c}$${\displaystyle n}$${\displaystyle rc}$${\displaystyle r=5}$${\displaystyle c=8}$${\displaystyle n=rc=40}$${\displaystyle r}$${\displaystyle c}$${\displaystyle S}$${\displaystyle S}$${\displaystyle A}$${\displaystyle B}$${\displaystyle n/2}$${\displaystyle r\leq c}$${\displaystyle S}$${\displaystyle r\leq {\sqrt {n}}}$${\displaystyle c\leq r}$${\displaystyle {\sqrt {n}}}$${\displaystyle S}$${\displaystyle {\sqrt {n}}}$${\displaystyle n/2}$

平面セパレータ定理は、任意の平面グラフで同様の分割を構築できることを述べています。任意の平面グラフの場合、グリッド グラフの場合と異なるのは、セパレータのサイズは ですが、 より大きくなる可能性があること、2 つの部分集合とのサイズの上限は(定理の最も一般的なバージョンでは)ではなく であること、2 つの部分集合と自体は連結された部分グラフを形成する必要がないことです。 ${\displaystyle O({\sqrt {n}})}$${\displaystyle {\sqrt {n}}}$${\displaystyle A}$${\displaystyle B}$${\displaystyle 2n/3}$${\displaystyle n/2}$${\displaystyle A}$${\displaystyle B}$

Lipton & Tarjan (1979) は、必要に応じて、与えられた平面グラフに辺を追加して、最大平面グラフ (平面埋め込みのすべての面が三角形) になるようにします。次に、任意の頂点 をルートとする幅優先探索を実行し、 からの距離によって頂点をレベルに分割します。 が中央レベル (上位レベルと下位レベルの頂点の数がどちらも最大 であるレベル)である場合、それぞれ より上と下のステップにあり、それぞれ頂点を含むレベルと が存在する必要があります。そうでない場合、 付近のレベルに個以上の頂点が存在することになります。彼らは、との和集合、幅優先探索木に属さず 2 つのレベルの間にある の辺の端点、および の端点からレベル に戻る2 つの幅優先探索木パス上の頂点によって形成されるセパレータが存在する必要があることを示しています。セパレータの頂点と2つの互いに素な部分グラフは線形時間で見つけることができる。^[4]${\displaystyle v}$${\displaystyle v}$${\displaystyle l_{1}}$${\displaystyle n/2}$${\displaystyle l_{0}}$${\displaystyle l_{2}}$${\displaystyle O({\sqrt {n}})}$${\displaystyle l_{1}}$${\displaystyle O({\sqrt {n}})}$${\displaystyle n}$${\displaystyle l_{1}}$${\displaystyle S}$${\displaystyle l_{0}}$${\displaystyle l_{2}}$${\displaystyle e}$${\displaystyle G}$${\displaystyle e}$${\displaystyle l_{0}}$${\displaystyle S}$${\displaystyle {\sqrt {8n}}\approx 2.83{\sqrt {n}}}$

セパレータ定理のこの証明は、各頂点が非負のコストを持つ重み付き平面グラフにも適用されます。グラフは、、 、 の3つの集合に分割でき、および はそれぞれ最大で総コストを持ち、およびからの辺を持たない頂点を持ちます。^[4]同様のセパレータ構成をより注意深く分析することにより、Djidjev (1982) は のサイズの上限を に減らすことができることを示しまし た。^[2]${\displaystyle A}$${\displaystyle S}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$${\displaystyle 2/3}$${\displaystyle S}$${\displaystyle O({\sqrt {n}})}$${\displaystyle A}$${\displaystyle B}$${\displaystyle S}$${\displaystyle {\sqrt {6n}}\approx 2.45{\sqrt {n}}}$

Holzer ら (2009) は、このアプローチの簡略版を提案しています。彼らはグラフを最大平面になるように拡張し、以前と同じように幅優先探索木を構築します。次に、木の一部ではない各辺について、その端点を結ぶ木パスと組み合わせてサイクルを形成します。次に、これらのサイクルの 1 つの頂点をセパレータとして使用します。このアプローチでは、直径の大きい平面グラフに対して小さなセパレータが見つかる保証はありませんが、実験では、多くの種類の平面グラフで Lipton–Tarjan および Djidjev の幅優先階層化法よりも優れていることが示されています。^[5]${\displaystyle e}$${\displaystyle e}$

すでに最大平面グラフであるグラフに対して、より強力な単純サイクルセパレータの構成を示すことが可能です。これは、サイクルの内側と外側（グラフの一意の平面埋め込み内）にそれぞれ最大で個の頂点があるような短いサイクルです。Miller (1986) は、リプトン・タージャン法を用いて、探索レベルが単純サイクルを形成する幅優先探索の修正版を使用して、これを（セパレータのサイズを として）証明しました。^[6]${\displaystyle 2n/3}$${\displaystyle {\sqrt {8n}}}$

Alon、Seymour、Thomas (1994) は、より直接的に単純なサイクル セパレータの存在を証明しています。 を、 の外側に最大で の頂点を持つ、最大で の頂点を持つサイクルとし、これが内部と外部を可能な限り均等に分割するものとしましょう。彼らは、これらの仮定により がセパレータになることを強制することを示しています。 そうでなければ、 内の距離はで囲まれたディスク内の距離に等しくなければなりません(ディスクの内部を通るより短い経路は、より良いサイクルの境界の一部を形成するでしょう)。 さらに、はちょうど の長さでなければなりません。そうでなければ、 の辺の 1 つを三角形の他の 2 辺で置き換えることによって改善できるからです。 の頂点に(時計回りに) から まで番号が付けられ、頂点 が頂点 と対応付けられている場合、平面グラフに対するメンガーの定理の形式で、これらの対応したペアをディスク内の頂点が互いに素な経路で接続できます。しかし、これらの経路の合計長さは を超えてしまうため、矛盾が生じます。彼らはさらにいくつかの研究を加えて、同様の方法で、最大で のサイズの単純なサイクルセパレータが存在することを示した。^[7]${\displaystyle C}$${\displaystyle {\sqrt {8n}}}$${\displaystyle 2n/3}$${\displaystyle C}$${\displaystyle C}$${\displaystyle C}$${\displaystyle C}$${\displaystyle C}$${\displaystyle {\sqrt {8n}}}$${\displaystyle C}$${\displaystyle 1}$${\displaystyle {\sqrt {8n}}}$${\displaystyle i}$${\displaystyle {\sqrt {8n}}-i+1}$${\displaystyle n}$${\displaystyle {\sqrt {9n/2}}\approx 2.12{\sqrt {n}}}$

Djidjev & Venkatesan (1997) は、単純サイクルセパレータ定理の定数係数をさらに に改良しました。彼らの方法は、セパレータのサイズが最大 である、非負の頂点重みを持つグラフの単純サイクルセパレータを見つけることができ、グラフの分割がより不均等になることを犠牲にして、より小さいサイズのセパレータを生成することができます。^{[8]最大でない}二連結平面グラフでは、面の長さのベクトルのユークリッドノルムに比例するサイズの単純サイクルセパレータが存在し、ほぼ線形時間で見つけることができます。^[9]${\displaystyle 1.97{\sqrt {n}}}$${\displaystyle 2{\sqrt {n}}}$

ケーベ・アンドレーエフ・サーストンの円充填定理によれば、任意の平面グラフは、互いに交わらない内部を持つ平面上の円板の充填によって表すことができ、グラフ内の2つの頂点が隣接するのは、対応する円板のペアが互いに接している場合に限る。ミラーら (1997) が示すように、このような充填では、最大で内部または内部に円板が接触し、最大で外部に円板が接触し、円板を横切る円が存在する。^[10]${\displaystyle 3n/4}$${\displaystyle 3n/4}$${\displaystyle O({\sqrt {n}})}$

これを証明するため、ミラーらは立体投影法を使用して、3 次元の単位球面上にパッキングをマッピングしています。投影法を注意深く選択することで、球の中心をその表面上の円板中心の中心点にすることができ、球の中心を通る任意の平面によって、球は 2 つの半空間に分割され、各半空間には最大で円板が含まれます (または、円板と交差します)。中心を通る平面が一様ランダムに選択されると、円板はその半径に比例した確率で交差します。したがって、交差する円板の期待数は、円板の半径の合計に比例します。ただし、半径の 2 乗の合計は円板の総面積に比例し、これは最大で単位球の表面積の合計 (定数) になります。ジェンセンの不等式に関する議論から、非負の実数の 2 乗の合計が定数で制限される場合、数自体の合計は であることが示されています。したがって、ランダムな平面が横切るディスクの期待数は であり、最大でその数のディスクを横切る平面が存在する。この平面は球面と大円で交差し、大円は平面内の目的の特性を持つ円に投影される。この円が横切るディスクは、円の内側にあるディスクを持つ頂点と円の外側にあるディスクを持つ頂点を分離する平面グラフセパレータの頂点に対応し、これら 2 つのサブセットにはそれぞれ最大で 個の頂点が含まれる。^[11]${\displaystyle 3n/4}$${\displaystyle n}$${\displaystyle O({\sqrt {n}})}$${\displaystyle O({\sqrt {n}})}$${\displaystyle O({\sqrt {n}})}$${\displaystyle 3n/4}$

この方法は、そのようなセパレータを線形時間で見つけるランダム化アルゴリズム[ ^10]と、同じ線形時間境界を持つ実用性は低いが決定論的アルゴリズム^{[12]につながります。}円充填の充填密度に関する既知の境界を使用してこのアルゴリズムを注意深く分析すると、最大でサイズ のセパレータを見つけられることが示されます^[13] この改善されたセパレータのサイズ境界は、グラフのより不均等な分割を犠牲にして実現されますが、Spielman & Teng (1996) は、Alon、Seymour & Thomas (1990) のセパレータと比較して、ネストされた分割の時間境界における定数係数が改善されていると主張しています。このセパレータのサイズは、実際には、ランダム切断面の不均一な分布を使用することでさらに改善できます。^[14] $${\displaystyle {\sqrt {\frac {2\pi }{\sqrt {3}}}}\left({\frac {1+{\sqrt {3}}}{2{\sqrt {2}}}}+o(1)\right){\sqrt {n}}\approx 1.84{\sqrt {n}}.}$$

ミラーらの議論における立体投影は、円板の中心の一定の割合を含む最小の円を考え、それを範囲内で一様に選んだ定数で拡大することで回避できる。ミラーらの場合と同様に、拡大された円と交差する円板は有効なセパレータを形成し、セパレータは適切なサイズであることが期待される。結果として得られる定数はやや悪い。^[15]${\displaystyle [1,2]}$

スペクトルクラスタリング法は、グラフの頂点をグラフから導出された行列の固有ベクトルの座標によってグループ化する手法で、非平面グラフのグラフ分割問題に対するヒューリスティックとして長い間使用されてきました。^[16] Spielman & Teng (2007) が示すように、スペクトルクラスタリングは、制限された次数を持つ平面グラフに適用される平面セパレータ定理の弱められた形式の別の証明を導くためにも使用できます。彼らの方法では、与えられた平面グラフの頂点は、グラフのラプラシアン行列の固有ベクトルの 2 番目の座標によってソートされ、このソートされた順序は、分割によって切断される辺の数と分割の小さい側の頂点の数の比が最小となる点で分割されます。彼らが示すように、制限された次数を持つすべての平面グラフには、このタイプの分割があり、その比は です。この分割はバランスが取れていないかもしれませんが、2辺のうち大きい方の辺内で分割を繰り返し、各繰り返しで形成されたカットの結合を取ると、最終的にはエッジを持つバランスの取れた分割につながります。これらのエッジの端点は、サイズ のセパレータを形成します。^[17]${\displaystyle O(1/{\sqrt {n}})}$${\displaystyle O({\sqrt {n}})}$${\displaystyle O({\sqrt {n}})}$

平面セパレータ定理のバリエーションには、グラフの頂点の2 つの部分集合との間にカットを形成する小さなエッジ セットであるエッジ セパレータが含まれます。2 つの集合と はそれぞれ、最大でグラフの頂点の数の定数分数のサイズを持つ必要があり(慣例的に、両方の集合のサイズは最大で です)、グラフの各頂点は と のどちらか一方に属します。セパレータは、 に 1 つの端点を持ち、 に 1 つの端点を持つエッジで構成されます。エッジ セパレータのサイズの境界には、グラフの頂点の数だけでなく頂点の次数も関係します。ホイール グラフやスター グラフなど、1 つの頂点が次数 である平面グラフには、線形以下の数のエッジを持つエッジ セパレータはありません。これは、どのエッジ セパレータも、高次数の頂点とカットの反対側の頂点を接続するすべてのエッジを含まなければならないためです。ただし、最大次数を持つすべての平面グラフには、サイズ のエッジ セパレータがあります。^[18]${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$${\displaystyle n}$${\displaystyle 2n/3}$${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$${\displaystyle n-1}$${\displaystyle \Delta }$${\displaystyle O({\sqrt {\Delta n}})}$

平面グラフの双対グラフ内の単純なサイクルセパレータは、元のグラフのエッジセパレータを形成します。^[19] Gazit & Miller (1990) の単純なサイクルセパレータ定理を与えられた平面グラフの双対グラフに適用すると、すべての平面グラフには、その頂点次数ベクトルのユークリッドノルムに比例するサイズのエッジセパレータがあることが示され、エッジセパレータのサイズの境界が強化されます。 ${\displaystyle O({\sqrt {\Delta n}})}$

Papadimitriou と Sideri (1996)は、グラフが穴のない、または一定数の穴があるグリッド グラフの誘導サブグラフである場合に、グラフを同じサイズの 2 つのサブグラフに分割する最小のエッジ セパレータを見つけるための多項式時間アルゴリズムを説明しています。ただし、彼らは、この問題は任意の平面グラフに対してNP 完全であると推測し、問題の複雑さは任意の数の穴があるグリッド グラフでも任意の平面グラフと同じであることを示しています。 ${\displaystyle G}$${\displaystyle G}$

グリッド グラフでは、点の集合は最大 個のグリッド点のサブセットを囲むことができます。最大値は、グリッドの角の近くに対角線上に配置することで達成されます。したがって、少なくとも個の点を残りのグリッドから分離するセパレータを形成するには、が少なくとも である必要があります。 ${\displaystyle {\sqrt {n}}\times {\sqrt {n}}}$${\displaystyle S}$${\displaystyle s<{\sqrt {n}}}$${\displaystyle s(s-1)/2}$${\displaystyle S}$${\displaystyle n/3}$${\displaystyle s}$${\displaystyle {\sqrt {2n/3}}\approx 0.82{\sqrt {n}}}$

残りのグラフを最大 頂点のサブグラフに分割するすべてのセパレータに対して、少なくとも頂点平面グラフが存在する（ の値が任意に大きい場合） 。^[2]構築には、球を凸多面体で近似し、多面体の各面を三角形のメッシュに置き換え、球の表面に 等周定理を適用することが含まれます。${\displaystyle n}$${\displaystyle n}$${\displaystyle S}$${\displaystyle 2n/3}$${\displaystyle S}$${\displaystyle {\sqrt {4\pi n/{\sqrt {27}}}}\approx 1.56{\sqrt {n}}}$

セパレータは、平面グラフのセパレータ階層、つまりより小さなグラフへの再帰的分解に組み合わせることができます。セパレータ階層は、ルート ノードが特定のグラフ自体を表し、ルートの 2 つの子が、 2 つのサブセットとセパレータから形成された誘導サブグラフの再帰的に構築されたセパレータ階層のルートであるバイナリ ツリーで表すことができます。 ${\displaystyle A}$${\displaystyle B}$

このタイプのセパレータ階層は、与えられたグラフのツリー分解の基礎を形成します。ツリー分解では、各ツリー ノードに関連付けられた頂点の集合は、そのノードからツリーのルートまでのパス上のセパレータの和集合です。グラフのサイズはツリーの各レベルで定数倍小さくなるため、セパレータのサイズの上限も各レベルで定数倍小さくなり、これらのパス上のセパレータのサイズは等比級数で に加算されます。つまり、このように形成されたセパレータの幅は であり、これを使用して、すべての平面グラフのツリー幅が であることを示すことができます。 ${\displaystyle O({\sqrt {n}})}$${\displaystyle O({\sqrt {n}})}$ ${\displaystyle O({\sqrt {n}})}$

バイナリツリーをトップダウンでトラバースし、バイナリツリーの各ノードに関連付けられた誘導されたサブグラフのそれぞれに線形時間の平面セパレータアルゴリズムを適用してセパレータ階層を直接構築すると、合計で時間がかかります。ただし、Lipton-Tarjan幅優先階層化アプローチを使用し、適切なデータ構造を使用して各パーティションステップを線形時間未満で実行することで、セパレータ階層全体を線形時間で構築することは可能です。 ^[20]${\displaystyle O(n\log n)}$

セパレータではなく分離に基づく関連タイプの階層を形成する場合、ルートノードの2つの子は、2つのサブグラフの再帰的に構築された階層と、指定されたグラフの分離のルートになります。この場合、全体の構造はツリー分解ではなく分岐分解になります。この分解における任意の分離の幅は、任意のノードから階層のルートまでのパス上のセパレータのサイズの合計によって制限されるため、このようにして形成された任意の分岐分解には幅があり、任意の平面グラフには分岐幅があります。他の多くの関連するグラフ分割問題は、平面グラフであってもNP完全ですが、平面グラフの最小幅の分岐分解を多項式時間で見つけることは可能です。^[21]${\displaystyle G_{1}}$${\displaystyle G_{2}}$${\displaystyle O({\sqrt {n}})}$ ${\displaystyle O({\sqrt {n}})}$

Fomin と Thilikos (2006a) は、Alon、Seymour、Thomas (1994) の方法をより直接的に分岐分解の構築に適用して、すべての平面グラフの分岐幅は最大で であり、これは Alon らの単純閉路分離定理の定数と同じであることを示しています。任意のグラフのツリー幅は最大でその分岐幅であるため、これは平面グラフのツリー幅が最大で であることも示しています。 ${\displaystyle 2.12{\sqrt {n}}}$${\displaystyle 3/2}$${\displaystyle 3.18{\sqrt {n}}}$

いくつかの疎グラフには、線形以下のサイズのセパレータがありません。拡張グラフでは、頂点の一定の割合を削除しても、接続されたコンポーネントは1つだけ残ります。^[22]

おそらく最も古いセパレータ定理は、Jordan (1869) によるもので、任意の木は、 1 つの頂点を削除することで、それぞれが最大 の頂点を持つサブツリーに分割できるというものです。 ^[10]特に、最大コンポーネント サイズを最小化する頂点にはこの特性があります。最大コンポーネント サイズを最小化する頂点でなければ、一意の大きなサブツリー内のその隣接頂点がさらに優れた分割を形成するためです。同じ手法を任意のグラフのツリー分解に適用すると、どのグラフにもそのツリー幅に等しいサイズのセパレータがあることを示すことができます。 ${\displaystyle n/2}$

グラフが平面ではないが、種数の表面に埋め込むことができる場合、そのグラフには頂点を持つセパレータがあります。Gilbert、Hutchinson、Tarjan (1984) は、Lipton と Tarjan (1979) と同様のアプローチを使用してこれを証明しています。彼らは、グラフの頂点を幅優先レベルにグループ化し、2 つのレベルを見つけます。これらのレベルを削除すると、少数のレベルからなる 1 つの大きなコンポーネントのみが残ります。この残りのコンポーネントは、種数に比例する数の幅優先パスを削除することで平面にすることができ、その後、残った平面グ​​ラフに Lipton–Tarjan 法を適用できます。結果は、削除された 2 つのレベルのサイズとそれらの間のレベルの数を慎重にバランスさせることによって得られます。グラフの埋め込みが入力の一部として与えられている場合、そのセパレータは線形時間で見つけることができます。種数 のグラフには、サイズ のエッジセパレータもあります。^[23]${\displaystyle G}$ ${\displaystyle g}$${\displaystyle O({\sqrt {gn}})}$${\displaystyle g}$${\displaystyle O({\sqrt {g\Delta n}})}$

有界種数のグラフは、マイナーを取る操作の下で閉じたグラフの族の例を形成し、セパレータ定理は任意のマイナー閉グラフ族にも適用されます。特に、グラフ族が頂点を持つ禁制マイナーを持つ場合、頂点を持つセパレータを持ち、そのようなセパレータは任意のに対して時間内に見つけることができます。^[24]${\displaystyle h}$${\displaystyle O(h{\sqrt {n}})}$${\displaystyle O(n^{1+\varepsilon })}$${\displaystyle \varepsilon >0}$

ミラーら (1997) の円セパレータ法は、空間内の任意の点が最大で定数個のボールで覆われるという性質を持つ任意の - 次元ボール系の交差グラフ、次元の-最近傍グラフ、^{[10] 、および}有限要素メッシュから生じるグラフに一般化されます。^[25]この方法で構築された球セパレータは、入力グラフを最大で頂点のサブグラフに分割します。 - 層ボール交差グラフと- 最近傍グラフのセパレータのサイズは です。^[10]${\displaystyle d}$${\displaystyle k}$${\displaystyle k}$${\displaystyle d}$${\displaystyle n(d+1)/(d+2)}$${\displaystyle k}$${\displaystyle k}$${\displaystyle O(k^{1/d}n^{1-1/d})}$

グラフの遺伝的族が、ある に対して、サイズ のセパレータを持つセパレータ定理を持つ場合、そのグラフは必然的に多項式展開、つまりその浅いマイナーの密度の多項式境界を持つ。逆に、多項式展開を持つグラフは、部分線形セパレータ定理を持つ。^[26]${\displaystyle n^{c}}$${\displaystyle c<1}$

セパレータ分解は、平面グラフ上の問題を解決するための効率的な分割統治アルゴリズムを設計する際に役立ちます。例として、この方法で解決できる問題の 1 つは、重み付き平面有向グラフの最短サイクルを見つけることです。これは次の手順で解決できます。

• 平面分離定理に従って、与えられたグラフを3つの部分集合、に分割する。${\displaystyle G}$${\displaystyle S}$${\displaystyle A}$${\displaystyle B}$
• 最短サイクルを再帰的に検索し、${\displaystyle A}$${\displaystyle B}$
• ダイクストラのアルゴリズムを使用して、内の各頂点について、内の最短サイクルを見つけます。${\displaystyle s}$${\displaystyle S}$${\displaystyle s}$${\displaystyle G}$
• 上記の手順で見つかったサイクルのうち最短のものを返します。

このアルゴリズムにおけるとの2 つの再帰呼び出しの時間は、ダイクストラ アルゴリズムの呼び出しを実行する時間によって大きく左右されるため、このアルゴリズムは時間内で最短のサイクルを見つけます。 ${\displaystyle A}$${\displaystyle B}$${\displaystyle O({\sqrt {n}})}$${\displaystyle O(n^{3/2}\log n)}$

同じ最短閉路問題に対する、 の時間で実行されるより高速なアルゴリズムが、Wulff-Nilsen (2009) によって与えられました。彼のアルゴリズムは、同じセパレータベースの分割統治構造を使用しますが、任意のセパレータではなく単純な閉路セパレータを使用するため、 の頂点は、閉路セパレータの内側と外側のグラフの単一の面に属します。次に、彼は、 ダイクストラのアルゴリズムへの個別の呼び出しを、より洗練されたアルゴリズムに置き換えて、平面グラフの単一の面にあるすべての頂点からの最短経路を見つけ、2 つのサブグラフからの距離を結合します。重み付きだが無向の平面グラフの場合、最短閉路は双対グラフの最小カットに等しく、 の時間で見つけることができます^[27] 。また、重みなしの無向平面グラフの最短閉路 (その内周) は、 の時間で見つけることができます。^[28] (ただし、重みなしグラフのより高速なアルゴリズムは、セパレータ定理に基づいていません。) ${\displaystyle O(n\log ^{3}n)}$${\displaystyle S}$${\displaystyle O({\sqrt {n}})}$${\displaystyle O(n\log \log n)}$${\displaystyle O(n)}$

Frederickson は、セパレータ定理を平面グラフに実装することにより、単一ソースの最短経路を求めるより高速な別のアルゴリズムを提案しました。^[29]これは、慎重に選択された頂点のサブセットに対する反復検索を伴う Dijkstra のアルゴリズムの改良版です。このバージョンは、-頂点グラフでは時間がかかります。セパレータは、グラフの分割、つまりエッジ セットを 2 つ以上のサブセット (領域と呼ばれる) に分割するために使用されます。領域のいずれかのエッジがノードに接する場合、そのノードは領域に含まれていると言われます。複数の領域に含まれるノードは、それを含む領域の境界ノードと呼ばれます。この方法では、 -ノード グラフの - 分割の概念を使用します。これは、境界ノードを含むノードを含む領域へのグラフ分割です。Frederickson は、セパレータ定理を再帰的に適用することで、- 分割を時間内に見つけることができることを示しまし た。 ${\displaystyle O(n{\sqrt {\log n}})}$${\displaystyle n}$${\displaystyle r}$${\displaystyle n}$${\displaystyle O(n/r)}$${\displaystyle O(r)}$${\displaystyle O({\sqrt {r}})}$${\displaystyle r}$${\displaystyle O(n\log n)}$

問題を解決するための彼のアルゴリズムの概要は次のとおりです。

1. 前処理フェーズ: グラフを慎重に選択された頂点のサブセットに分割し、これらのサブセット内のすべての頂点のペア間の最短経路を決定します。この経路上の中間頂点はサブセット内にありません。このフェーズでは、平面グラフを3 より大きい次数を持つ頂点なしでに変換する必要があります。オイラーの公式の系から、結果のグラフの頂点の数は になります。ここで、 は内の頂点の数です。このフェーズでは、適切な -分割の次の特性も保証されます。平面グラフの適切な-分割とは、次の -分割 です。${\displaystyle G_{0}}$${\displaystyle G}$${\displaystyle n\leq 6n_{0}-12}$${\displaystyle n_{0}}$${\displaystyle G_{0}}$${\displaystyle r}$${\displaystyle r}$${\displaystyle r}$
   • 各境界頂点は最大3つの領域に含まれ、
   • 連結されていない領域は連結されたコンポーネントで構成され、そのすべてが 1 つまたは 2 つの連結された領域のまったく同じセットと境界頂点を共有します。
2. 検索フェーズ:
   • 主な目的: ソースからサブセット内の各頂点までの最短距離を見つけます。サブセット内の頂点が閉じている場合、から までのパスが存在するように、サブセット内のすべての頂点の暫定距離を更新する必要があります。${\displaystyle v}$${\displaystyle d(w)}$${\displaystyle w}$${\displaystyle v}$${\displaystyle w}$
   • モップアップ: 残りのすべての頂点までの最短距離を決定します。

Henzinger らは、非負の辺長の平面グラフにおける単一ソース最短経路アルゴリズムのために Frederickson の - 分割手法を拡張し、線形時間アルゴリズムを提案した。^[30]彼らの方法は Frederickson のグラフ分割の概念を一般化したものであって、 - ノード グラフの - 分割は領域への分割であり、各領域には最大で境界ノードが含まれる。 - 分割が繰り返して小さな領域に分割される場合、それは再帰分割と呼ばれる。このアルゴリズムは、おおよそ レベルの分割を使用する。ここで、 は反復対数関数を表す。再帰分割は、葉が の異なる辺でラベル付けされた根付き木によって表される。木の根はのすべてからなる領域を表し、根の子はその領域が分割されるサブ領域を表す、などである。各葉(原子領域) は、正確に 1 つの辺を含む領域を表す。 ${\displaystyle r}$${\displaystyle (r,s)}$${\displaystyle n}$${\displaystyle O(n/r)}$${\displaystyle r^{O(1)}}$${\displaystyle s}$${\displaystyle (r,s)}$${\displaystyle \log ^{*}n}$${\displaystyle \log ^{*}}$${\displaystyle G}$${\displaystyle G}$

ネストされた分解は、有限要素法から生じるもののような平面グラフ構造を持つ疎対称線形方程式系を解くための、ガウス消去法のセパレータベースの分割統治バリエーションです。この方法では、方程式系を記述するグラフのセパレータを見つけ、セパレータによって互いに分離された2つのサブ問題の変数を再帰的に消去し、次にセパレータ内の変数を削除します。^[31]この方法のフィルイン（結果として得られる行列のコレスキー分解の非ゼロ係数の数）は であり、^[32]この方法は同じ問題に対する反復法と競合することができます。 ^[31] ${\displaystyle O(n\log n)}$

Klein、Mozes、Weimann ^[33]は、負の閉路を含まない正と負の弧長を持つ有向平面グラフについて、ソース頂点から他のすべての頂点までの最短経路距離を見つける、時間線形空間アルゴリズムを提示した。彼らのアルゴリズムは、平面グラフセパレータを使用して、とノードの間が で囲まれるようなノード（弧なし）を通過するジョルダン曲線を見つける。通過するノードは境界ノードである。元のグラフは、平面埋め込みを に沿って切断し、境界ノードを複製することで、2つのサブグラフと に分割される。各グラフの境界ノードは、単一の面 の境界上に位置する。 ${\displaystyle O(n\log ^{2}n)}$${\displaystyle s}$ ${\displaystyle C}$${\displaystyle O({\sqrt {n}})}$${\displaystyle n/3}$${\displaystyle 2n/3}$${\displaystyle C}$${\displaystyle C}$${\displaystyle G}$${\displaystyle G_{0}}$${\displaystyle G_{1}}$${\displaystyle C}$${\displaystyle G_{i}}$${\displaystyle F_{i}}$

彼らのアプローチの概要は以下の通りです。

• 再帰呼び出し: 最初の段階では、各グラフ内から距離を再帰的に計算します。${\displaystyle r}$${\displaystyle G_{i}}$
• 部分内境界距離: 各グラフについて、境界ノード間のすべての距離を計算します。これには時間がかかります。${\displaystyle G_{i}}$${\displaystyle G_{i}}$${\displaystyle O(n\log n)}$
• 単一ソースのパート間境界距離: の最短経路は、と の間を行ったり来たりして、からすべての境界ノードまでの の距離を計算します。 交互の反復では、と のすべての境界距離を使用します。 反復回数は で、このステージの全体時間は です。ここで、 は逆アッカーマン関数です。${\displaystyle G}$${\displaystyle G_{0}}$${\displaystyle G_{1}}$${\displaystyle G}$${\displaystyle r}$${\displaystyle G_{0}}$${\displaystyle G_{1}}$${\displaystyle O({\sqrt {n}})}$${\displaystyle O(n\alpha (n))}$${\displaystyle \alpha (n)}$
• 単一ソースのパート間距離: 前の段階で計算された距離は、各 G _iの修正バージョン内での Dijkstra 計算とともに使用され、からすべてのノードまで の距離が計算されます。この段階には時間がかかります。${\displaystyle G}$${\displaystyle r}$${\displaystyle O(n\log n)}$
• 単一ソース距離の再ルート:からの距離は非負の長さに変換され、再びダイクストラのアルゴリズムを使用してからの距離が計算されます。この段階には時間がかかります。${\displaystyle r}$${\displaystyle G}$${\displaystyle s}$${\displaystyle O(n\log n)}$

このアルゴリズムの重要な部分は、価格関数と短縮長の使用です。弧の長さが である有向グラフの場合、価格関数は のノードから実数への関数です。弧 の場合、 に関する短縮長はです。実行可能な価格関数は、 のすべての弧で非負の短縮長を誘導する価格関数です。これは、正と負の長さを含む最短経路問題を非負の長さのみを含む問題に変換するのに役立ち、その後、ダイクストラのアルゴリズムを使用して解決できます。 ${\displaystyle G}$${\displaystyle \ell (uv)}$${\displaystyle \varphi }$${\displaystyle G}$${\displaystyle uv}$${\displaystyle \varphi }$${\displaystyle \ell _{\varphi }(uv)=\ell (uv)+\varphi (u)-\varphi (v)}$${\displaystyle G}$

セパレータベースの分割統治パラダイムは、動的グラフアルゴリズム[ ^34]やポイントロケーション^[35]、多角形三角測量^[20] のアルゴリズム、最短経路^[36]、最近傍グラフの構築^[37]、平面グラフの最大独立集合の近似アルゴリズム^[35]のデータ構造の設計にも使用されています。

平面グラフの木分解または枝分解に動的計画法を使用することで、多くのNP困難な最適化問題を指数関数の時間でまたはで解くことができます。たとえば、この形式の境界は、最大独立集合、シュタイナー木、ハミルトン閉路を見つけることや、平面グラフ上の巡回セールスマン問題を解くために知られています。^{[38]幾何学的グラフの分離定理を含む同様の方法は、同じ形式の時間境界でユークリッド巡回セールスマン問題と}シュタイナー木構築問題を解くために使用できます。^[39]${\displaystyle {\sqrt {n}}}$${\displaystyle {\sqrt {n}}\log n}$

平面性を維持し、入力グラフを入力パラメータに線形なサイズのカーネルに縮小するカーネル化を許容するパラメータ化された問題の場合、このアプローチを使用して、実行時間が入力グラフのサイズに多項式的に依存し、 （アルゴリズムのパラメータ）に指数的に依存する固定パラメータの扱いやすいアルゴリズムを設計できます。たとえば、この形式の時間境界は、サイズ の頂点カバーと支配集合を見つけることで知られています。^[40]${\displaystyle {\sqrt {k}}}$${\displaystyle k}$${\displaystyle k}$

Lipton & Tarjan (1980) は、セパレータ定理を使用して、最大独立集合 を見つけるなどの平面グラフ上のNP 困難な最適化問題に対する多項式時間近似スキームを取得できることを観察しました。具体的には、セパレータ階層を適切なレベルで切り捨てることにより、サイズ のセパレータを見つけることができ、これを除去すると、任意の定数 に対して、グラフが最大 のサイズのサブグラフに分割されます。4色定理により、サイズが 以上の独立集合が存在するため、削除されたノードは最大独立集合の無視できる割合を形成し、残りのサブグラフの最大独立集合は、サイズの指数関数的な時間で独立に見つけることができます。このアプローチを、セパレータ階層構築のための後の線形時間手法^[20]と、同型サブグラフ間の独立集合の計算を共有するためのテーブル検索と組み合わせると、最適値の 倍以内のサイズの独立集合を線形時間で構築できるようになります。ただし、この係数よりも 1 にさらに近い近似比の場合、Baker (1994) の後のアプローチ (平面セパレータではなくツリー分解に基づく) では、時間と近似品質のトレードオフがより適切になります。 ${\displaystyle O(n/{\sqrt {\log n}})}$${\displaystyle c\log n}$${\displaystyle c}$${\displaystyle n/4}$${\displaystyle 1-1/{\sqrt {\log n}}}$

同様のセパレータベースの近似方式は、頂点カバーなどの他の困難な問題を近似するためにも使用されています。^[41] Aroraら(1998)は、重み付き平面グラフ上の最短経路メトリックの巡回セールスマン問題を近似するために、セパレータを別の方法で使用しています。彼らのアルゴリズムは、セパレータ階層の各レベルでセパレータを制限回数だけ交差する最短ツアーを見つけるために動的計画法を使用し、交差制限が増加するにつれて、このように構築されたツアーの長さが最適ツアーに近似することを示しています。

セパレータは、少数のビットを使用して平面グラフやその他の分離可能なグラフを表すデータ圧縮アルゴリズムの一部として使用されています。これらのアルゴリズムの基本原理は、数を選択し、セパレータを使用して、指定された平面グラフを、セパレータ内に頂点を持つ最大 のサイズのサブグラフに繰り返し分割することです。 を適切に選択すると(最大で の対数に比例する)、非同型- 頂点平面サブグラフの数は、分解内のサブグラフの数よりも大幅に少なくなるため、すべての可能性のある非同型サブグラフのテーブルを作成し、セパレータ分解内の各サブグラフをテーブルへのインデックスで表すことによって、グラフを圧縮できます。セパレータ頂点によって形成されるグラフの残りの部分は、明示的に表現することも、同じデータ構造の再帰バージョンを使用して表現することもできます。この方法を使用すると、平面グラフや、より制限されたグラフのファミリーを、情報理論的に最適なビット数でエンコードできます。つまり、表現するグラフのファミリーに - 頂点グラフがある場合、そのファミリー内の個々のグラフは、ビットのみを使用して表現できます。^[42]また、クエリに対する回答を表す追加の表形式の情報でサブグラフのテーブルを拡張することで、クエリごとに定数時間で頂点間の隣接性をテストし、頂点の次数を決定し、頂点の隣接をリストできるこのタイプの表現を構築することもできます。^[43]${\displaystyle k}$${\displaystyle O(n/k)}$${\displaystyle k}$${\displaystyle O(n/{\sqrt {k}})}$${\displaystyle k}$${\displaystyle n}$ ${\displaystyle k}$${\displaystyle P_{n}}$ ${\displaystyle n}$${\displaystyle (1+o(1))\log _{2}P_{n}}$

グラフ族のユニバーサルグラフは、グラフのすべてのメンバーをサブグラフとして含むグラフです。セパレータは、-頂点平面グラフが頂点と辺を持つユニバーサルグラフを持つことを示すために使用できます。^[44]${\displaystyle {\mathcal {F}}}$${\displaystyle {\mathcal {F}}}$${\displaystyle n}$${\displaystyle n}$${\displaystyle O(n^{3/2})}$

構築には、セパレータの 3 つの頂点サブセットのサイズがグラフ構造に依存しない、セパレータ定理の強化された形式が含まれます。つまり、最大で定数倍の絶対値を持つ数 が存在し、これにより、すべての- 頂点平面グラフの頂点は、から への辺がなく、、を持つサブセット、 、に分割できます。これは、セパレータ定理の通常の形式を使用してグラフを繰り返し分割し、分割のすべてのコンポーネントを頂点未満の 2 つのサブセットに配置できるようにしてから、必要に応じてこれらのサブセットからセパレータに頂点を移動して、指定されたサイズになるまで続けることで示されます。 ${\displaystyle c}$${\displaystyle {\sqrt {n}}}$${\displaystyle n}$${\displaystyle A}$${\displaystyle S}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$${\displaystyle |S|=c}$${\displaystyle |A|=|B|=(n-c)/2}$${\displaystyle n/2}$

このようなセパレータ定理が示されると、これを使用して、やはりグラフ構造に依存しない - 頂点平面グラフのセパレータ階層を作成できます。この階層から形成されるツリー分解には幅があり、任意の平面グラフに使用できます。このツリー分解内の、ツリー分解の共通ノードに属するすべての頂点のペアの集合は、すべての - 頂点平面グラフをサブグラフとして含む頂点を持つ自明な完全グラフを形成します。同様の構成により、制限次数平面グラフには、エッジを持つユニバーサル グラフがあり、 O 表記に隠された定数は次数の制限に依存していることが示されます。平面グラフ (または無制限次数のツリー) のユニバーサル グラフには、必ずエッジがあります。^[44]${\displaystyle n}$${\displaystyle O({\sqrt {n}})}$${\displaystyle O(n^{3/2})}$${\displaystyle n}$${\displaystyle O(n\log n)}$${\displaystyle \Omega (n\log n)}$

Esperet、Joret、Morin（2020）は、セパレーターを使用した構造を改善して、 とすることができると発表しました。 ${\displaystyle O(n^{3/2})}$${\displaystyle n^{1+o(1)}}$

• 頂点セパレータ
• 幾何学的セパレーター