平面セパレータ定理 – 日本語百科事典辞書

Planar_separator_theorem
グラフ理論における平面セパレータ定理は、平面グラフの等周不等式の一形式であり、少数の頂点を削除することで平面グラフをより小さな部分に分割できることを示します。具体的には、 ○ ( n)
{ O({sqrt {n}})}
n頂点グラフ ( Oがbig O 表記法を呼び出す)の頂点は、グラフを互いに素なサブグラフに分割できます。2 n / 3
{ 2n/3}
頂点。
セパレータ定理の弱い形式 ○ ( n
ログ3 / 2 n )
{ O({sqrt {n}}log ^{3/2}n)}
代わりにセパレータ内の頂点 ○ ( n)
{ O({sqrt {n}})}
は最初にUngar (1951)によって証明され、セパレータのサイズに厳密に漸近束縛された形式は、Lipton & Tarjan (1979)によって最初に証明されました。彼らの研究以来、セパレータ定理はさまざまな方法で非難されてきました。 ○ ( n)
{ O({sqrt {n}})}
定理の項が改良され、特定のクラスの非平面グラフに拡張されました。
セパレータ定理を繰り返し適用すると、グラフのツリー分解またはブランチ分解のいずれかの形式をとるセパレータ階層が生成されます。セパレータ階層を使用して、平面グラフの効率的な分割統治アルゴリズムを考案することができ、これらの階層での動的プログラミングを使用して、これらのグラフのNP 困難な最適化問題を解決するための指数時間および固定パラメータの扱いやすいアルゴリズムを考案できます。セパレータ階層は、有限要素法から生じる線形方程式の疎な系を解くためのガウス消去法の効率的な変形である入れ子解剖でも使用できます。
平面グラフ以外にも、セパレータ定理は、固定マイナーグラフ、最近傍グラフ、有限要素メッシュを除くグラフなど、他のクラスのグラフに適用されています。グラフのクラスに対する分離定理の存在は、ツリー幅と多項式展開の概念によって形式化および定量化できます。
コンテンツ
1 定理の説明
2 例
3 構造物
3.1 幅優先の階層化 3.2 シンプルなサイクルセパレータ 3.3 円区切り記号 3.4 スペクトル分割 3.5 エッジセパレーター
4 下限
5 区切り文字の階層
6 他のクラスのグラフ
7 アプリケーション
7.1 分割統治アルゴリズム 7.2 NP 困難最適化問題の厳密な解法 7.3 近似アルゴリズム 7.4 グラフ圧縮 7.5 ユニバーサルグラフ
8 こちらも参照
9 ノート
10 参考文献

定理の説明
通常言われているように、セパレータ定理は次のように述べています。 n { n}
$n""$ -頂点平面グラフG =( V E ) { G=(V，E)}

の頂点のパーティションが存在します。 G { G}

3つのセットに分けてあ { A}
S
{ S}

、と B { B}

、それぞれがあ { A}
と B
{ B}

多くても2 n / 3
{ 2n/3}

頂点、 S { S}

もっている ○ ( n)
{ O({sqrt {n}})}

頂点があり、1 つの端点を持つエッジはありません。あ { A}

そして 1 つのエンドポイント B { B}

。必須ではありませんあ { A}

また B { B}

接続された部分グラフを形成する G { G}
S
{ S}

は、このパーティションのセパレータと呼ばれます。
同等の定式化は、任意のエッジの n { n}
-頂点平面グラフ G { G}

2 つのエッジの共通部分グラフに再分割される可能性がありますG 1
{ G_{1}}
と G 2
{ G_{2}}

両方のサブグラフが少なくともn / 3
{ n/3}

頂点など、2 つの部分グラフの頂点セットの交差部分が次のようになります。 ○ ( n)
{ O({sqrt {n}})}

その中の頂点。このようなパーティションは、セパレーションとして知られています。分離が指定されている場合、頂点セットの交差部分がセパレーターを形成し、一方のサブグラフに属するが他方には属さない頂点は、それぞれが最大で次の値を持つ分離されたサブセットを形成します。2 n / 3
{ 2n/3}

頂点。逆に、1 つに 3 つのセットへの分割が与えられた場合、あ { A}
S
{ S}

、と B { B}

平面セパレータ定理の条件を満たす場合、端点を持つエッジが次のような分離を形成する可能性があ { A}

に属するG 1
{ G_{1}}

、端点を持つエッジ B { B}

に属するG 2
{ G_{2}}

、および残りのエッジ (両方の端点が S { S}

）は任意に分割されます。
定数2 / 3
{ 2/3}

セパレータ定理のステートメントにおけるは任意であり、開区間内の他の数値に置き換えることができます。( 1/ 2 1 )
{ (1/2，1)}

定理の形を変えることなく、より均等な部分集合への分割は、不均一な分割内の大きなセットを繰り返し分割し、結果として得られる連結成分を再グループ化することによって、不均等な分割から取得できます。

例

グリッドグラフの平面セパレーター
次のグリッドグラフを考えてみましょう。 r { r}

行と c { c}

列。人数、個数、総数 n { n}

頂点の数が等しいr c
{ rc}

。たとえば、図では、r = 5
{ r=5}
c= 8
{ c=8}

、とn = r c = 40
{ n=rc=40}

。もしも r { r}

が奇数の場合は中央の行が 1 つあり、それ以外の場合は中心に等しく近い 2 つの行が同様に、もし c { c}

が奇数の場合は中央の列が 1 つあり、それ以外の場合は中央に等しく近い 2 つの列が選択する S { S}

これらの中央の行または列のいずれかになり、削除する S { S}

グラフから、グラフを 2 つの小さな接続されたサブグラフに分割します。あ { A}
と B
{ B}

、それぞれは最大でn / 2
{ n/2}

頂点。もしもr ≤ c
{ rleq c}
(図のように)、中央の列を選択すると区切り文字が表示されます。 S { S}
と r ≤ n
{ rleq {sqrt {n}}}

頂点、および同様にc ≤ r
{ cleq r}

次に、中央の行を選択すると、最大で次のセパレータが与えられます。 n { {sqrt {n}}}

頂点。したがって、すべてのグリッドグラフにはセパレータが S { S}

せいぜいサイズの n { {sqrt {n}}}

を削除すると、それぞれのサイズが最大の 2 つの接続されたコンポーネントに分割されます。n / 2
{ n/2}
。平面セパレータ定理は、任意の平面グラフでも同様のパーティションを構築できることを示しています。任意の平面グラフの場合は、セパレータのサイズがグリッドグラフの場合とは異なります。 ○ ( n)
{ O({sqrt {n}})}

しかし、それよりも大きくなる可能性があります n { {sqrt {n}}}

、2 つのサブセットのサイズの限界あ { A}
と B
{ B}
(定理の最も一般的なバージョンでは) は2 n / 3
{ 2n/3}

それよりもn / 2
{ n/2}

、および 2 つのサブセットあ { A}
と B
{ B}

それ自体が接続されたサブグラフを形成する必要はありません。

構造物

幅優先の階層化
Lipton & Tarjan (1979) は、必要に応じて追加のエッジによって特定の平面グラフを拡張し、最大平面になります (平面埋め込み内のすべての面が三角形になります)。次に、任意の頂点をルートとして幅優先検索を実行します。 v { v}

からの距離に応じて頂点をレベルに分割します。 v { v}

。もしもI 1
{ l_{1}}

中央レベル (高いレベルと低いレベルの頂点の数が両方とも最大以下であるようなレベル)n / 2
{ n/2}

）その場合はレベルが存在する必要がありますI 0
{ l_{0}}
と I 2
{ l_{2}}

それは ○ ( n)
{ O({sqrt {n}})}

上下のステップI 1
{ l_{1}}

それぞれ、およびそれを含む ○ ( n)
{ O({sqrt {n}})}

そうしないと、次の頂点よりも多くの頂点が存在することになります。 n { n}

近くのレベルの頂点I 1
{ l_{1}}

。区切り文字が必要であることを示しています S { S}

～の組合によって結成されたI 0
{ l_{0}}
と I 2
{ l_{2}}

、エッジの端点 e { e}
G
{ G}

これは幅優先探索ツリーに属さず、2 つのレベルの間にあり、その端点からの 2 つの幅優先探索ツリーパス上の頂点です。 e { e}

レベルに戻るI 0
{ l_{0}}

。セパレーターのサイズ S { S}

このように構築されたのはせいぜい
8 n ≈2.83 n
{ {sqrt {8n}}約 2.83{sqrt {n}}}

。セパレータと 2 つの互いに素な部分グラフの頂点は、線形時間で見つけることができます。
セパレータ定理のこの証明は、各頂点が負でないコストを持つ重み付き平面グラフにも同様に当てはまります。グラフは 3 つのセットに分割できますあ { A}
S
{ S}

、と B { B}

そのようなあ { A}
と B
{ B}

それぞれが最大でも2 / 3
{ 2/3}

総費用のうち、 S { S}

もっている ○ ( n)
{ O({sqrt {n}})}

頂点、エッジなしあ { A}
と B
{ B}

。 Djidjev (1982) は、同様のセパレータ構造をより注意深く分析することにより、セパレータのサイズの限界が S { S}

に減らすことができます
6 n ≈2.45 n
{ {sqrt {6n}}約 2.45{sqrt {n}}}
。ホルツァーら。（2009)は、このアプローチの簡略版を提案しています。彼らは、グラフを最大平面になるように拡張し、以前と同様に幅優先探索ツリーを構築します。次に、各エッジについて e { e}

それはツリーの一部ではなく、組み合わせることによってサイクルを形成します。 e { e}

エンドポイントを接続するツリーパスを使用します。次に、これらのサイクルの 1 つの頂点をセパレータとして使用します。このアプローチは、直径の大きな平面グラフに対して小さなセパレータを見つけることを保証できませんが、彼らの実験では、このアプローチが多くの種類の平面グラフに対してリプトン・タルジャン法およびジジェフの幅優先階層化法よりも優れていることが示されています。

シンプルなサイクルセパレータ
すでに最大の平面であるグラフの場合、単純なサイクルセパレータのより強力な構造を示すことができます。これは、サイクルの内側と外側 (グラフの固有の平面埋め込み内) がそれぞれ次の位置にあるような短い長さのサイクルです。多くの2 n / 3
{ 2n/3}

頂点。Miller (1986) はこれを証明しています (セパレータのサイズは
8 n { {sqrt {8n}}}

）幅優先検索の修正バージョンにリプトン・タルジャン手法を使用し、検索のレベルが単純なサイクルを形成します。
Alon、Seymour、および Thomas (1994) は、単純なサイクル分離子の存在をより直接的に証明しています。 C { C}

最大でも
8 n { {sqrt {8n}}}

頂点の数は最大でも2 n / 3
{ 2n/3}

外側の頂点 C { C}

、それは内部と外部の可能な限り均等なパーティションを形成し、これらの仮定が強制することを示しています。 C { C}

区切り文字になります。それ以外の場合は、以内の距離 C { C}

で囲まれた円盤内の距離と等しくなければなりません C { C}
(ディスクの内部を通る経路が短いほど、より良いサイクルの境界の一部が形成されます)。さらに、 C { C}

正確な長さでなければなりません
8 n { {sqrt {8n}}}

そうでない場合は、エッジの 1 つを三角形の他の 2 つの辺で置き換えることで改善できる可能性が頂点が C { C}

から（時計回りに）番号が付けられます。 1 {表示スタイル 1}
8 n { {sqrt {8n}}}

、頂点 I { i}

頂点と一致しています
8 n −I + 1
{ {sqrt {8n}}-i+1}

の場合、これらの一致したペアは、平面グラフのメンジャーの定理の形式により、円盤内の頂点の共通点のないパスによって接続できます。ただし、これらのパスの合計の長さは必然的に次の値を超えます。 n { n}

、矛盾です。追加の作業を加えて、同様の方法で、最大でも次のサイズの単純なサイクルセパレータが存在することを示します。
9 n /2 2.12 n
{ {sqrt {9n/2}}約 2.12{sqrt {n}}}
。 Djidjev & Venkatesan (1997) は、単純なサイクルセパレータ定理の定数因数をさらに改良し、1.97 n
{ 1.97{sqrt {n}}}

。彼らの方法では、最大でもセパレータサイズが負でない頂点重みを持つグラフの単純なサイクルセパレータを見つけることもできます。2 n
{ 2{sqrt {n}}}

、グラフのより不均一な分割を犠牲にして、より小さいサイズのセパレータを生成できます。最大ではない二重接続平面グラフでは、ほぼ線形時間で見つけることができる面の長さのベクトルのユークリッドノルムに比例するサイズを持つ単純なサイクルセパレータが存在します。

円区切り記号
コーベ・アンドレーエフ・サーストンの円パッキング定理によれば、任意の平面グラフは、対応する円板のペアが存在する場合にのみ、グラフ内の 2 つの頂点が隣接するように、内部が互いに素である平面内の円形ディスクのパッキングによって表現できます。相互に接しています。ミラーらのように、(1997)は、そのようなパッキングの場合、最大で次の円が存在することを示しています。3 n / 4
{ 3n/4}

せいぜいディスクが接触しているか内部にある3 n / 4
{ 3n/4}

ディスクが接触またはその外側にあり、それが交差する ○ ( n)
{ O({sqrt {n}})}

ディスク。
これを証明するために、Miller et al. 立体投影法を使用して、充填物を単位球の表面に 3 次元でマッピングします。投影法を慎重に選択することで、球の中心をその表面上の円盤の中心の中心点にすることができ、球の中心を通る平面が、それぞれが含むか最大で交差する 2 つの半空間に分割します。3 n / 4
{ 3n/4}

ディスクの。中心を通る平面が均一にランダムに選択された場合、円盤はその半径に比例した確率で交差します。したがって、交差するディスクの予想数は、ディスクの半径の合計に比例します。ただし、半径の二乗の合計は円盤の総面積に比例し、最大でも単位球の総表面積である定数になります。ジェンセンの不等式に関する議論は、次のことを示しています。 n { n}

非負の実数は定数によって制限され、数値自体の合計は次のようになります。 ○ ( n)
{ O({sqrt {n}})}

。したがって、ランダムな平面が横切るディスクの予想数は次のようになります。 ○ ( n)
{ O({sqrt {n}})}

そして最大でもその数の円盤を横切る平面が存在します。この平面は大円で球と交差し、必要な特性を持つ平面内の円に投影されます。の ○ ( n)
{ O({sqrt {n}})}

この円が横切る円盤は、円の内側にある円盤の頂点と円の外側にある円盤の頂点を分ける平面グラフセパレーターの頂点に対応します。3 n / 4
{ 3n/4}

これら 2 つのサブセットのそれぞれにある頂点。
この方法は、線形時間でそのようなセパレータを見つけるランダム化アルゴリズムと、同じ線形時間制限を使用するあまり実用的ではない決定論的アルゴリズムにつながります。円パッキングのパッキング密度に関する既知の境界を使用してこのアルゴリズムを慎重に分析することにより、最大でも次のサイズのセパレーターを見つけることができます2 π 3 (1+3 2 + ああ( 1) ) n ≈ 1.84
n{ {sqrt {frac {2pi }{sqrt {3}}}}left({frac {1+{sqrt {3}}}{2{sqrt {2}}} }+o(1)right){sqrt {n}}約 1.84{sqrt {n}}.}

この改良されたセパレータサイズ限界はグラフのより不均一な分割を犠牲にしていますが、Spielman & Teng (1996) は、Alon、Seymour &のセパレータと比較して、ネストされた分析の時間限界における定数係数が改善されていると主張しています。トーマス (1990)。実際には、ランダムな切断面に不均一な分布を使用することで、製造されるセパレータのサイズをさらに改善できます。
Miller et al.の立体投影法は、この議論は、円盤の中心の一定部分を含む最小の円を考慮し、その範囲内で均一に選択された定数でそれを拡張することで回避できます。
[ 1 2 】 { }

。Miller らの場合と同様、展開された円と交差するディスクは有効なセパレータを形成しており、期待どおり、セパレータのサイズは適切です。結果として得られる定数は若干悪くなります。

スペクトル分割
グラフの頂点がグラフから導出された行列の固有ベクトルの座標によってグループ化されるスペクトルクラスタリング手法は、非平面グラフのグラフ分割問題のヒューリスティックとして長い間使用されてきました。 Spielman & Teng （2007)が示すように、スペクトルクラスタリングは、次数が制限された平面グラフに適用される平面セパレータ定理の弱体化形式の代替証明を導き出すためにも使用できます。彼らの方法では、与えられた平面グラフの頂点は、グラフのラプラシアン行列の固有ベクトルの 2 番目の座標によってソートされ、このソートされた順序は、パーティションによってカットされるエッジの数の比率が最小になる点でパーティション化されます。パーティションの小さい方の頂点の数に合わせます。示されているように、有界次数のすべての平面グラフには、このタイプの分割があり、比率は次のようになります。 ○ ( 1/ n)
{ O(1/{sqrt {n}})}

。この分割はバランスが取れていない可能性がありますが、2 つの辺のうち大きい方で分割を繰り返し、各繰り返しで形成されたカットを結合すると、最終的にはバランスの取れた分割が得られます。 ○ ( n)
{ O({sqrt {n}})}

エッジ。これらのエッジの端点は、次のサイズのセパレータを形成します。 ○ ( n)
{ O({sqrt {n}})}

。

エッジセパレーター
平面セパレータ定理のバリエーションには、エッジセパレータ、つまり 2 つのサブセット間のカットを形成する小さなエッジのセットが含まれます。あ { A}
と B
{ B}

グラフの頂点の数。2つのセットあ { A}
と B
{ B}

それぞれのサイズは最大でも数値の定数分数でなければなりません n { n}

グラフの頂点の数 (従来、両方のセットのサイズは最大でも2 n / 3
{ 2n/3}

)、グラフの各頂点は次のいずれかに正確に属します。あ { A}
と B
{ B}

。セパレータは、1 つの端点を持つエッジで構成されます。あ { A}

そして 1 つのエンドポイント B { B}

。エッジセパレータのサイズの境界には、グラフ内の頂点の次数と頂点の数が関係します。平面グラフでは、1 つの頂点が次数を持ちます。n − 1
{ n-1}

ホイールグラフやスターグラフを含むには、サブリニア数のエッジを持つエッジセパレータがありません。これは、エッジセパレータには、高次の頂点をカットの反対側の頂点に接続するすべてのエッジが含まれている必要があるためです。ただし、最大次数を持つすべての平面グラフ Δ { Delta }

サイズのエッジセパレータがあります ○ ( Δ n) { O({sqrt {Delta n}})}
。平面グラフの二重グラフ内の単純なサイクルセパレータは、元のグラフのエッジセパレータを形成します。 Gazit & Miller (1990)の単純なサイクルセパレータ定理を特定の平面グラフの双対グラフに適用すると、 ○ ( Δ n) { O({sqrt {Delta n}})}

すべての平面グラフには、そのサイズが頂点次数のベクトルのユークリッドノルムに比例するエッジセパレータがあることを示すことで、エッジセパレータのサイズの限界を決定します。
Papadimitriou & Sideri (1996) は、グラフを分割する最小のエッジセパレーターを見つけるための多項式時間アルゴリズムについて説明しています。 G { G}

同じサイズの 2 つの部分グラフに分割する場合、 G { G}

は、穴がないか、一定数の穴があるグリッドグラフの誘導サブグラフです。しかし、彼らは、この問題は任意の平面グラフに対してNP 完全であると推測し、問題の複雑さは任意の平面グラフの場合と同様に、任意の数の穴を持つグリッドグラフに対しても同じであることを示しました。

下限

正二十面体の各面を 100 個の三角形のメッシュで置き換えることによって形成される多面体。ジジェフ (1982 年)の下限構造の例
で n { {sqrt {n}}time {sqrt {n}}}

グリッドグラフ、セット S { S}
s< n
{ s<{sqrt {n}}}

ポイントは最大でもサブセットを囲むことができます s ( s− 1 ) / 2
{ s(s-1)/2}

格子点を配置することで最大値が得られる点 S { S}

グリッドの角近くの対角線に。したがって、少なくとも分離するセパレータを形成するには、n / 3
{ n/3}

残りのグリッドからのポイントのうち、 s { s}

少なくとも必要です
2 n /3 0.82 n
{ {sqrt {2n/3}}約 0.82{sqrt {n}}}
が存在します n { n}
-頂点平面グラフ (任意の大きな値の場合) n { n}

) そのように、すべての区切り文字に対して S { S}

残りのグラフを最大で 1 つのサブグラフに分割します。2 n / 3
{ 2n/3}

頂点、 S { S}

少なくとも
4π n / 27 ≈ 1.56 n
{ {sqrt {4pi n/{sqrt {27}}}}約 1.56{sqrt {n}}}

。構築には、球を凸多面体で近似し、多面体の各面を三角形メッシュで置き換え、球の表面に等周定理を適用することが含まれます。

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

セパレーターの。
このタイプのセパレータ階層は、指定されたグラフのツリー分解の基礎を形成します。各ツリーノードに関連付けられた頂点のセットは、そのノードからツリーのルートまでのパス上のセパレータの結合です。グラフのサイズはツリーの各レベルで一定の係数で減少するため、セパレータのサイズの上限も各レベルで一定の係数で減少するため、これらのパス上のセパレータのサイズが追加されます。幾何級数_ _ ○ ( n)
{ O({sqrt {n}})}

。すなわち、このようにして形成されたセパレータは、幅を有する。 ○ ( n)
{ O({sqrt {n}})}

、すべての平面グラフにツリー幅があることを示すために使用できます。 ○ ( n)
{ O({sqrt {n}})}
バイナリツリーをトップダウンでトラバースし、バイナリツリーの各ノードに関連付けられた誘導サブグラフのそれぞれに線形時間平面セパレータアルゴリズムを適用することにより、セパレータ階層を直接構築するには、合計で次の時間がかかります。 ○ ( n
ログn )
{ O(nlog n)}

時間。ただし、Lipton-Tarjan の幅優先階層化アプローチを使用し、適切なデータ構造を使用して各パーティションステップをサブリニア時間で実行することにより、セパレータ階層全体を線形時間で構築することは可能です。
セパレータではなく区切りに基づいて関連タイプの階層を形成する場合、ルートノードの 2 つの子が 2 つのサブグラフに対して再帰的に構築された階層のルートになります。G 1
{ G_{1}}
と G 2
{ G_{2}}

指定されたグラフの分離の場合、全体の構造はツリー分解ではなくブランチ分解を形成します。この分解における分離の幅は、やはり、任意のノードから階層のルートまでのパス上のセパレーターのサイズの合計によって制限されるため、この方法で形成された分岐分解には幅が ○ ( n)
{ O({sqrt {n}})}

そして、どの平面グラフにも分岐幅が ○ ( n)
{ O({sqrt {n}})}

。関連する他の多くのグラフ分割問題は、平面グラフであってもNP 完全ですが、多項式時間で平面グラフの最小幅の分岐分解を見つけることは可能です。
Alon、Seymour & Thomas (1994)の方法を分岐分解の構築に直接適用することにより、Fomin & Thilikos （2006a) は、すべての平面グラフが最大でも分岐幅を持つことを示しています。2.12 n
{ 2.12{sqrt {n}}}

、Alon らの単純なサイクルセパレータ定理の定数と同じ定数です。どのグラフのツリー幅も最大で3 / 2
{ 3/2}

これは、平面グラフのツリー幅が最大であることも示しています。3.18 n
{ 3.18{sqrt {n}}}
他のクラスのグラフ

一部のスパースグラフにはサブリニアサイズのセパレータがありません。エキスパンダーグラフでは、頂点の一定部分まで削除しても、連結成分が 1 つだけ残ります。
おそらく知られている最も古いセパレータ定理は、任意のツリーを最大でサブツリーに分割できるというJordan (1869)の結果です。n / 2
{ n/2}

単一の頂点を削除することでそれぞれの頂点を作成します。特に、コンポーネントの最大サイズを最小化する頂点にはこの特性がそうでない場合、固有の大きなサブツリー内のその隣接頂点がさらに優れたパーティションを形成するからです。同じ手法を任意のグラフのツリー分解に適用すると、どのグラフにも最大でもそのTreewidthに等しいサイズのセパレータがあることを示すことができます。
グラフの場合 G { G}

平面ではありませんが、属の表面に埋め込むことができます g { g}

、その後は区切り文字があります ○ ( g n) { O({sqrt {gn}})}

頂点。Gilbert、Hutchinson、Tarjan (1984) は、 Lipton & Tarjan (1979)と同様のアプローチを使用してこれを証明しています。彼らは、グラフの頂点を幅優先レベルにグループ化し、2 つのレベルを見つけます。これらのレベルを削除すると、少数のレベルで構成される最大 1 つの大きなコンポーネントが残ります。この残りのコンポーネントは、属に比例するいくつかの幅優先パスを削除することによって平面にすることができ、その後、リプトン・タージャン法を残りの平面グラフに適用できます。結果は、削除された 2 つのレベルのサイズと、それらの間のレベルの数とのバランスを慎重にとった結果として得られます。グラフの埋め込みが入力の一部として指定されている場合、そのセパレーターは線形時間で見つけることができます。属のグラフ g { g}

サイズのエッジセパレータもあります ○ ( gΔ n)
{ O({sqrt {gDelta n}})}
。有界属数のグラフは、マイナーを取得する操作の下で閉じられたグラフ族の例を形成し、セパレータ定理は任意のマイナーで閉じられたグラフ族にも適用されます。特に、グラフファミリに禁止されたマイナーが含まれている場合、 h { h}

頂点の場合はセパレータがあります ○ ( h n) { O(h{sqrt {n}})}

頂点、そのようなセパレーターは時間内に見つかります ○ ( n1 +
ε)
{ O(n^{1+varepsilon })}

誰にとってもε > 0
{ varepsilon >0}
0″”> 。
ディスクの交差グラフ。k = 5
{ k=5}

平面の任意の点をカバーするディスク
Millerらの円セパレーター法。(1997) は、任意のシステムの交差グラフに一般化します。 d { d}
– 空間内の任意の点が最大でも何らかの定数でカバーされるという性質を持つ次元のボール k { k}

ボールの、へ k { k}
-最近隣グラフ d { d}

次元、、および有限要素メッシュから生じるグラフに適用されます。このように構築された球セパレーターは、入力グラフを最大で 1 つのサブグラフに分割します。 n ( d+ 1 ) /( d+ 2 )
{ n(d+1)/(d+2)}

頂点。セパレータのサイズ k { k}
-プライボール交差グラフと k { k}
-最近傍グラフは ○ ( k1 / d n 1 − 1 / d)
{ O(k^{1/d}n^{1-1/d})}
。遺伝的なグラフ族に、次のサイズのセパレータを含むセパレータ定理がある場合n c
{ n^{c}}

、いくつかのためのc < 1
{ c<1}

の場合、必然的に多項式展開、つまり浅いマイナーの密度に束縛された多項式が存在します。逆に、多項式展開を伴うグラフには線形未満のセパレータ定理が

アプリケーション

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

3つのサブセットに分ける S { S}
あ
{ A}
B
{ B}

平面セパレータ定理によると
最短サイクルを再帰的に検索します。あ { A}

と B { B}

ダイクストラのアルゴリズムを使用して頂点ごとに検索します s { s}
S
{ S}

、最短サイクルスルー s { s}
G
{ G}
上記の手順で見つかったサイクルのうち最短のものを返します。
への 2 つの再帰呼び出しにかかる時間あ { A}
と B
{ B}

このアルゴリズムでは、実行時間によって支配されます。 ○ ( n)
{ O({sqrt {n}})}

はダイクストラのアルゴリズムを呼び出すため、このアルゴリズムは次の最短サイクルを見つけます。 ○ ( n3 / 2 グ n )
{ O(n^{3/2}log n)}

時間。
同じ最短サイクルの問題を時間内に実行する、より高速なアルゴリズム ○ ( n
ログ3 n )
{ O(nlog ^{3}n)}

、Wulff-Nilsen （2009)によって与えられました。彼のアルゴリズムは、同じセパレータベースの分割統治構造を使用しますが、任意のセパレータではなく単純なサイクルセパレータを使用するため、頂点は次のようになります。 S { S}

サイクルセパレータの内側と外側のグラフの 1 つの面に属します。その後、彼は ○ ( n)
{ O({sqrt {n}})}

ダイクストラのアルゴリズムをより高度なアルゴリズムで個別に呼び出して、平面グラフの 1 つの面上のすべての頂点からの最短パスを見つけ、2 つのサブグラフからの距離を結合します。重み付きだが無向平面グラフの場合、最短サイクルは双対グラフの最小カットに相当し、次のようになります。 ○ ( n
ログ
ログn )
{ O(nlog log n)}

時間、、および重み付けされていない無向平面グラフの最短サイクル (その周囲長) は時間内に見つかる可能性が ○ ( n ) { O(n)}

。 (ただし、重み付けされていないグラフの高速アルゴリズムはセパレータ定理に基づい)
Frederickson は、平面グラフにセパレータ定理を実装することにより、単一ソースの最短パスに対する別の高速アルゴリズムを提案しました。これは、慎重に選択された頂点のサブセットを反復検索するダイクストラのアルゴリズムを改良したものです。このバージョンでは、 ○ ( n
ログ n) { O(n{sqrt {log n}})}

の時間 n { n}
-頂点グラフ。セパレータは、グラフの分割、つまり、領域と呼ばれる 2 つ以上のサブセットへのエッジセットの分割を見つけるために使用されます。領域の一部のエッジがノードに入射する場合、ノードは領域に含まれていると言われます。複数の領域に含まれるノードを、それを含む領域の境界ノードと呼びます。このメソッドでは、次の概念を使用します。 r { r}
-分割 n { n}
– グラフを分割したノードグラフ ○ ( n/ r )
{ O(n/r)}

それぞれの領域に含まれる領域 ○ ( r ) { O(r)}

ノードを含む ○ ( r)
{ O({sqrt {r}})}

境界ノード。フレデリクソンは、 r { r}
-部門は次の場所にあります ○ ( n
ログn )
{ O(nlog n)}

セパレータ定理の再帰的適用による時間。
この問題を解決するための彼のアルゴリズムのスケッチは次のとおりです。
前処理フェーズ: グラフを慎重に選択した頂点のサブセットに分割し、これらのサブセット内の頂点のすべてのペア間の最短パスを決定します。ただし、このパス上の中間頂点はサブセットに含まれません。このフェーズでは平面グラフが必要ですG 0
{ G_{0}}

に変身する G { G}

3 を超える次数を持つ頂点はありません。オイラーの公式の帰結から、結果として得られるグラフの頂点の数は次のようになります。n ≤ 6 n 0 − 12
{ nleq 6n_{0}-12}

、どこn 0
{ n_{0}}

の頂点の数ですG 0
{ G_{0}}

。このフェーズでは、適切な製品の次の特性も保証します。 r { r}
-分割。適切な r { r}
-平面グラフの分割は r { r}
-そのような分割、
各境界頂点は最大 3 つの領域に含まれ、
接続されていない領域は接続されたコンポーネントで構成され、そのすべてが 1 つまたは 2 つの接続された領域のいずれかのまったく同じセットと境界頂点を共有します。
検索フェーズ:
Main Thrust: ソースからサブセット内の各頂点までの最短距離を見つけます。頂点のとき v { v}
サブセット内が閉じている場合、暫定的な距離 d ( w ) { d(w)}
すべての頂点 w { w}
からのパスが存在するようなサブセット内 v { v}
に w { w}
。
モップアップ: 残りのすべての頂点までの最短距離を決定します。
ヘンツィンガーら。フレデリクソン病を拡張した r { r}

非負のエッジ長に対する平面グラフにおける単一ソース最短経路アルゴリズムの分割手法と、線形時間アルゴリズムを提案しました。彼らの方法は、フレデリクソンのグラフ分割の概念を一般化したもので、次のようになります。( r s ) { (r，s)}
-分割 n { n}
-node グラフは次の分割です。 ○ ( n/ r )
{ O(n/r)}

それぞれの領域に含まれる領域r ○( 1 ) { r^{O(1)}}

ノードの数は、それぞれ最大で s { s}

境界ノード。もし( r s ) { (r，s)}
-division は、より小さな領域に繰り返し分割されます。これは、再帰的分割と呼ばれます。このアルゴリズムでは、およそ
ログ∗ n
{ log ^{*}n}

部門のレベル、ここで
ログ ∗ { log ^{*}}

は反復対数関数を示します。再帰的な分割は、葉が明確なエッジによってラベル付けされた根付きのツリーによって表されます。 G { G}

。ツリーのルートは、次のものすべてから構成される領域を表します。 G { G}

、ルートの子は、その領域が分割されるサブ領域などを表します。各リーフ(原子領域) は、エッジを 1 つだけ含む領域を表します。
ネストされた解析は、有限要素法から生じるものなど、平面グラフ構造を持つ疎対称線形方程式系を解くための、ガウス消去法のセパレーターベースの分割統治のバリエーションです。これには、方程式系を表すグラフのセパレータを見つけ、セパレータによって互いに分離されている 2 つの部分問題の変数を再帰的に削除し、次にセパレータ内の変数を削除することが含まれます。この方法のフィルイン (行列のコレスキー分解の結果として得られる非ゼロ係数の数) は次のとおりです。 ○ ( n
ログn )
{ O(nlog n)}

，この方法は、同じ問題に対して反復法と競合することができます。
クライン、モーゼス、ワイマンは、 ○ ( n
ログ2 n )
{ O(nlog ^{2}n)}
– ソース頂点からの最短パス距離を見つけるための時間、線形空間アルゴリズム s { s}

負のサイクルを含まない正および負の弧長を持つ有向平面グラフの他のすべての頂点に。彼らのアルゴリズムは平面グラフセパレータを使用してジョルダン曲線を見つけます C { C}

通過するもの ○ ( n)
{ O({sqrt {n}})}

間に次のようなノード (アークなし)n / 3
{ n/3}
と 2 n / 3
{ 2n/3}

ノードは次のように囲まれています C { C}

。経由するノード C { C}

パスは境界ノードです。元のグラフ G { G}

2 つのサブグラフに分かれていますG 0
{ G_{0}}
と G 1
{ G_{1}}

平面埋め込みを沿って切断することによって C { C}

そして境界ノードを複製します。各グラフの境界ノードG I
{ G_{i}}

単一の面の境界上にあるF I
{ F_{i}}
彼らのアプローチの概要は以下のとおりです。
再帰呼び出し: 最初のステージでは、からの距離を再帰的に計算します。 r { r}

各グラフ内でG I
{ G_{i}}
部品内境界距離: 各グラフごとG I
{ G_{i}}

すべての距離を計算しますG I
{ G_{i}}

境界ノード間。これにはかかります ○ ( n
ログn )
{ O(nlog n)}

時間。
単一ソースのパーツ間の境界距離: の最短パス G { G}

間を行き来しますG 0
{ G_{0}}

とG 1
{ G_{1}}

の距離を計算するには G { G}
ら r
{ r}

すべての境界ノードに。交互の反復では、次のすべての境界距離を使用します。G 0
{ G_{0}}

とG 1
{ G_{1}}

。反復回数は ○ ( n ) { O({sqrt {n}})}

、このステージの合計時間は次のとおりです。 ○ ( n α ( n) )
{ O(nalpha (n))}
こ α( n ) { alpha (n)}

は逆アッカーマン関数です。
単一ソースの部品間距離: 前の段階で計算された距離は、各 Gi の修正バージョン内のダイクストラ計算とともに使用され、次の距離を計算します。 G { G}
ら r
{ r}

すべてのノードに。この段階にかかるのは、 ○ ( n
ログn )
{ O(nlog n)}

時間。
単一ソース距離の再ルート: からの距離 r { r}
G
{ G}

は非負の長さに変換され、再びダイクストラのアルゴリズムを使用してからの距離が計算されます。 s { s}

。この段階で必要となるのは、 ○ ( n
ログn )
{ O(nlog n)}

時間。
このアルゴリズムの重要な部分は、価格関数の使用と長さの短縮です。有向グラフの場合 G { G}

弧長付き ℓ ( あなたv )
{ ell (uv)}

、価格関数は関数です φ { varphi }

のノードから G { G}

実数に。円弧の場合
あなた v { uv}

、に関して短縮された長さ φ { varphi }
は ℓ φ( あなたv ) = ℓ( あなたv ) + φ( あなた) − φ( v ) { ell _{varphi }(uv)=ell (uv)+varphi (u)-varphi (v)}

。実現可能な価格関数は、すべての円弧上で非負の短縮長を引き起こす価格関数です。 G { G}

。これは、正と負の長さが関係する最短経路問題を、非負の長さのみが関係する最短経路問題に変換し、ダイクストラのアルゴリズムを使用して解くのに役立ちます。
セパレーターベースの分割統治パラダイムは、動的グラフアルゴリズムと点位置ポリゴン三角形分割アルゴリズム最短パスおよび最近傍グラフの構築のためのデータ構造の設計にも使用されています。、、および平面グラフの最大独立セットの近似アルゴリズム。

NP 困難最適化問題の厳密な解法
平面グラフのツリー分解またはブランチ分解で動的プログラミングを使用することにより、多くのNP 困難な最適化問題を時間指数関数的に解決できる可能性が n { {sqrt {n}}}

また
nグ n
{ {sqrt {n}}log n}

。たとえば、この形式の境界は、最大独立集合、シュタイナー木、およびハミルトニアンサイクルを見つけたり、平面グラフ上の巡回セールスマン問題を解決したりすることで知られています。幾何学グラフのセパレータ定理を含む同様の方法を使用して、同じ形式の時間制限内でユークリッド巡回セールスマン問題とシュタイナー木構築問題を解くことができます。
平面性を維持し、入力グラフを入力パラメーターの線形サイズのカーネルに縮小するカーネル化を許容するパラメーター化された問題の場合、このアプローチを使用して、実行時間が多項式でサイズに依存する固定パラメーターの扱いやすいアルゴリズムを設計できます。入力グラフと指数関数的オン k { {sqrt {k}}}

、どこ k { k}

アルゴリズムのパラメータです。たとえば、この形式の時間境界は、頂点カバーを見つけたり、サイズのセットを支配したりすることで知られています。 k { k}

。

近似アルゴリズム
Lipton & Tarjan (1980)は、セパレータ定理を使用して、最大独立集合を求めるなど、平面グラフ上のNP 困難な最適化問題の多項式時間近似スキームを取得できることを観察しました。具体的には、セパレータ階層を適切なレベルで切り詰めることにより、次のサイズのセパレータを見つけることができます。 ○ ( n / ログ n) { O(n/{sqrt {log n}})}

グラフを最大サイズのサブグラフに分割するパーティションの削除 c ログ n { clog n}

、任意の定数に対して c { c}

。4 色定理によれば、少なくともサイズの独立した集合が存在します。n / 4
{ n/4}

したがって、削除されたノードは最大独立集合の無視できる部分を形成し、残りのサブグラフ内の最大独立集合は、そのサイズが時間的に指数関数的に独立して見つけることができます。このアプローチを、セパレータ階層構築のための後の線形時間法と、同型部分グラフ間の独立集合の計算を共有するためのテーブルルックアップと組み合わせることで、次の係数内でサイズの独立集合を構築することができます。1 − 1 /
ログ n { 1-1/{sqrt {log n}}}

線形時間で最適化されます。ただし、この係数よりもさらに 1 に近い近似比の場合、 Baker (1994)の後のアプローチ(平面セパレーターではなくツリー分解に基づく) では、時間と近似の品質のより良いトレードオフが提供されます。
同様のセパレータベースの近似スキームは、頂点カバーなどの他の困難な問題を近似するためにも使用されています。アローラら。(1998)別の方法でセパレータを使用して、加重平面グラフ上の最短パスメトリックの巡回セールスマン問題を近似します。彼らのアルゴリズムは、動的プログラミングを使用して、セパレータ階層の各レベルで境界回数セパレータを横切る最短のツアーを見つけます。また、交差境界が増加するにつれて、この方法で構築されたツアーは最適な長さに近似する長さになることを示しています。旅行。

グラフ圧縮
セパレータは、少数のビットを使用して平面グラフやその他の分離可能なグラフを表現するためのデータ圧縮アルゴリズムの一部として使用されてきました。これらのアルゴリズムの基本原理は、数値を選択することです。 k { k}

そして、セパレータを使用して指定された平面グラフを繰り返し分割します。 ○ ( n/ k )
{ O(n/k)}

最大でも同じサイズのサブグラフ k { k}

、と ○ ( n/ k)
{ O(n/{sqrt {k}})}

セパレータ内の頂点。適切な選択をすることで、 k { k}
(最大でも次の対数に比例します) n { n}

)非同型の数 k { k}
-vertex planar subgraphs は、分解のサブグラフの数よりも大幅に少ないため、考えられるすべての非同型サブグラフのテーブルを構築し、テーブルへのインデックスによってセパレータ分解の各サブグラフを表すことによって、グラフを圧縮できます。セパレータ頂点によって形成されるグラフの残りの部分は、明示的に表すことも、同じデータ構造の再帰バージョンを使用することによって表すこともできます。この方法を使用すると、平面グラフやさらに多くの制限されたグラフ族を、情報理論的に最適なビット数を使用してエンコードできます。P n
{ P_{n}}
n { n}
– 表現されるグラフのファミリー内の頂点グラフの場合、ファミリー内の個々のグラフは、( 1 + ああ( 1) )
ログ2 n { (1+o(1))log _{2}P_{n}}

ビット。サブグラフのテーブルを追加の表形式の情報で拡張することにより、頂点間の隣接性をテストし、頂点の次数を決定し、クエリごとに一定時間で頂点の近傍をリストするこのタイプの表現を構築することも可能です。クエリに対する回答を表します。

ユニバーサルグラフ
家族向けの普遍的なグラフ F { {mathcal {F}}}

グラフのすべてのメンバーを含むグラフです。 F { {mathcal {F}}}

サブグラフとして。区切り文字を使用して、 n { n}
-頂点平面グラフには、次のようなユニバーサルグラフが n { n}

頂点と ○ ( n3 / 2)
{ O(n^{3/2})}

エッジ。
この構築には、セパレータ定理の強化された形式が含まれており、セパレータ内の頂点の 3 つのサブセットのサイズはグラフ構造に依存しません。 c { c}

、その大きさは最大でも定数倍 n { {sqrt {n}}}

、すべての頂点が n { n}
-頂点平面グラフはサブセットに分割可能あ { A}
S
{ S}

、と B { B}

、からのエッジなしあ { A}
B
{ B}

、と| S | = c
{ |S|=c}

、そして| あ | = | B | =( n− c ) / 2
{ |A|=|B|=(nc)/2}

。これは、セパレータ定理の通常の形式を繰り返し使用して、パーティションのすべてのコンポーネントが 2 つのサブセットに配置できるまでグラフを分割することによって示すことができます。n / 2
{ n/2}

次に、必要に応じて頂点をこれらのサブセットからセパレーターに移動し、所定のサイズになるまで続けます。
このタイプのセパレータ定理が示されると、それを使用して次のセパレータ階層を生成できます。 n { n}
– 頂点平面グラフ。これもグラフ構造に依存しません。この階層から形成されるツリー分解には幅が ○ ( n)
{ O({sqrt {n}})}

あらゆる平面グラフに使用できます。このツリー分解の共通ノードに属する、このツリー分解内の頂点のすべてのペアのセットは、次のような自明のことながら完璧なグラフを形成します。 ○ ( n3 / 2)
{ O(n^{3/2})}

すべてを含む頂点 n { n}
-頂点平面グラフをサブグラフとして。同様の構造は、次数制限のある平面グラフが次のような普遍的なグラフを持つことを示しています。 ○ ( n
ログn )
{ O(nlog n)}

エッジ。ここで、 O 表記に隠された定数は次数限界に依存します。平面グラフのユニバーサルグラフ (または無制限の次数のツリーの場合でも) には、次のものが必要です。 Ω ( n
ログn )
{ Omega (nlog n)}

エッジ。
Esperet、Joret、Morin （2020) は次のように発表しました。 ○ ( n3 / 2)
{ O(n^{3/2})}

セパレーターを使用した構造を改善することができます。n 1 +
ああ( 1 ) { n^{1+o(1)}}
こちらも参照

頂点セパレーター
幾何学的な区切り文字

ノート
^ アロン、シーモア、トーマス (1990)。
^ ジジェフ (1982)。
^ ジョージ (1973)。George は、グリッドグラフの行または列を使用する代わりに、行と列の和集合をセパレータとして使用して、グラフを 4 つの部分に分割します。
^ リプトンとタージャン (1979)。
^ ホルツァーら。（2009)。
^ ミラー (1986)。
^ アロン、シーモア、トーマス (1994)。
^ ジジェフとヴェンカテサン (1997)。
^ ガジット＆ミラー (1990)。
^ ミラーら。(1997)。
^ ミラーら。(1997) ; パッチとアガルワル (1995)
^ エップスタイン、ミラー、テン (1995)。
^ スピルマンとテン (1996)。
^ グレンバン、ミラー、テン (1997)。
^ ハーペルド（2011)。
^ ドナス&ホフマン (1972) ; フィードラー (1973)。
^ スピルマンとテン（2007)。
^ Miller (1986) は2 接続平面グラフについてこの結果を証明し、 Diks et al. (1993)はそれをすべての平面グラフに拡張しました。
^ ミラー (1986) ; ガジット＆ミラー (1990)。
^ グッドリッチ (1995)。
^ シーモアとトーマス (1994)。
^ リプトンとタージャン (1979) ; エルデシュ、グラハム、シェメレディ (1976)
^ Sýkora & Vrt’o (1993)。
^ 河原林＆リード（2010)。未成年閉鎖家族における区切りに関する以前の研究については、 Alon、Seymour & Thomas (1990)、 Plotkin、Rao & Smith (1994)、およびReed & Wood （2009)を参照して
^ ミラーら。(1998)。
^ ドヴォルザークとノリン（2016)。
^ ウッチキとサンコウスキー（2011)。
^ チャン＆ルー（2011)。
^ フレデリクソン (1987)。
^ ヘンツィンガーら。(1997)。
^ ジョージ (1973)。
^ リプトン、ローズ、タージャン (1979) ; ギルバートとタージャン (1986 )
^ クライン、モーゼス、ワイマン（2010)。
^ エップスタインら。(1996) ; エップスタインら。(1998)。
^ リプトンとタージャン (1980)。
^ クラインら。(1994) ; タザリとミュラー・ハンネマン（2009 )
^ フリーズ、ミラー、テン (1992)。
^ ベルン (1990) ; デイネコ、クリンツ、ヴォーギンガー（2006) ; ドーンら。（2005) ; リプトンとタージャン (1980 )
^ スミスとウォーマルド (1998)。
^ アルバー、フェルナウ、ニーダーマイヤー（2003) ; フォミンとティリコス（2006b)。
^ バル＝イェフダとイーブン (1982) ; 千葉・西関・斉藤 (1981)。
^ 彼、カオ、ルー（2000)。
^ ブランドフォード、ブレロック、カッシュ（2003) ; ブレロックとファルザン（2010)。
^ Babai et al. (1982) ; バットら。(1989) ; チョン (1990)。

参考文献
アルバー、ヨッヘン。フェルナウ、ヘニング。Niedermeier、Rolf （2003)、「グラフセパレーター: パラメーター化されたビュー」、Journal of Computer and System Sciences、67 (4): 808–832、doi : 10.1016/S0022-0000(03)00072-2
アロン，ノガ; ポール・シーモア; Thomas、Robin (1990)、「非平面グラフの分離定理」、Journal of the American Mathematical Society、3 (4): 801–808、doi : 10.1090/S0894-0347-1990-1065053-0
アロン，ノガ; ポール・シーモア; Thomas、Robin (1994)、「Planar separators」、SIAM Journal on Discrete Mathematics、7 (2): 184–193、doi : 10.1137/S0895480191198768
Arora，サンジーヴ; グリニ、ミケランジェロ。デビッド・カーガー；クライン、フィリップ。Woloszyn、Andrzej (1998)、「加重平面グラフ TSP の多項式時間近似スキーム」、Proc. 第 9 回離散アルゴリズムに関する ACM-SIAM シンポジウム (SODA ’98)、33–41 ページ、ISBN 9780898714104
ババイ、L. ; チョン，フリーク州; エルデシュ、P. ; グラハム，ロータリー州; Spencer， JH (1982)、「すべてのスパースグラフを含むグラフについて」、Rosa， Alexander; Sabidussi，ゲルト; Jean Turgeon (編)、「組合せ論の理論と実践: 60 歳の誕生日を記念してアントンコッツィヒを称える記事集 (PDF)」、Annals of Discrete Mathematics、vol. 12、21–26ページ
Baker、Brenda S. (1994)、「平面グラフ上の NP 完全問題の近似アルゴリズム」、Journal of the ACM、41 (1): 153–180、doi : 10.1145/174644.174650、S2CID 9706753
バル＝イェフダ、R. Even、S. (1982)、「平面グラフの頂点カバーの近似について」、Proc. 第 14 回 ACM コンピューティング理論に関するシンポジウム (STOC ’82) : 303–309、doi : 10.1145/800070.802205、ISBN 0-89791-070-2、S2CID 2820550
Bern、Marshall (1990)、「平面ネットワークにおけるシュタイナーツリーの正確なアルゴリズムの高速化」、Networks、20 (1): 109–120、doi : 10.1002/net.3230200110
バット、サンディープ N. チョン・ファン RK ; レイトン， FT ; Rosenberg、Arnold L. (1989)、「有界次数ツリーおよび平面グラフのユニバーサルグラフ」 (PDF)、離散数学に関する SIAM ジャーナル、2 (2): 145、doi : 10.1137/0402014
ブランドフォード、ダニエル K. ブロック、ガイ E. Kash、Ian A. （2003)、「分離可能なグラフのコンパクト表現」、Proc. 第 14 回離散アルゴリズムに関する ACM-SIAM シンポジウム (SODA ’03) (PDF)、pp. 679–688
ブロック、ガイ E. Farzan、Arash （2010)、「分離可能なグラフの簡潔な表現」、Amir、Amihood にて。パリダ、ラクシュミ（編）、Ｐｒｏｃ．第21回組合せパターンマッチングシンポジウム、計算機科学講義録、vol.2 6129、Springer-Verlag、pp. 138–150、Bibcode : 2010LNCS.6129..138B、CiteSeerX 10.1.1.307.6710、doi : 10.1007/978-3-642-13509-5_13、ISBN 978-3-642-13508-8
チャレルムスク、パリニャ。ファクチャロエンポル、ジッタット。Nanongkai、Danupon （2004)、「平面グラフの最小カットを見つけるための決定論的近線形時間アルゴリズム」、Proc. 第 15 回離散アルゴリズムに関する ACM–SIAM シンポジウム (SODA’04)、pp. 828–829
チャン・シェンチー; Lu、Hsueh-I （2011)、「線形時間における平面グラフの周囲の計算」、SIAM Journal on Computing、42 (3): 1077–1094、arXiv : 1104.4892、doi : 10.1137/110832033、S2CID 2493979
千葉則重；西関貴雄; 斉藤信次 (1981)、「リプトンとタージャンの平面分離定理の応用」 (PDF)、情報処理ジャーナル、4 (4): 203–207
Chung、Fan RK (1990)、「分離定理とその応用」、Korte、Bernhard ; Lovász，ラスロー; プロメル、ハンス・ユルゲン。他。(編)、Paths、Flows、および VLSI-Layout、Algorithms and Combinatorics、vol. 9、シュプリンガー版、 17–34ページ、ISBN 978-0-387-52685-0
ディーネコ、ウラジミール G. クリンツ、ベッティーナ。Woeginger、Gerhard J. （2006)、「平面グラフにおけるハミルトンサイクル問題の正確なアルゴリズム」、Operations Research Letters、34 (3): 269–274、doi : 10.1016/j.orl.2005.04.013
ディックス、K。ジジェフ、ハンガリー州。シコラ、O. Vrt’o， I. (1993)、「アプリケーションを使用した平面および外側平面グラフのエッジセパレーター」、Journal of Algorithms、14 (2): 258–279、doi : 10.1006/jagm.1993.1013
Djidjev、HN (1982)、「平面グラフの分割問題について」、代数的および離散的手法に関する SIAM ジャーナル、3 (2): 229–240、doi : 10.1137/0603022
ジジェフ、フリスト N. Venkatesan、Shankar M. (1997)、「単純なサイクルグラフ分離のための定数の削減」、Acta Informatica、34 (3): 231–243、doi : 10.1007/s002360050082、S2CID 8406777
ドナス、私たち。Hoffman， AJ (1972)、「接続行列の固有ベクトルに基づくグラフとコンピューターロジックの分割アルゴリズム」、IBM Techn. 開示ブル。、15 : 938–944、 Spielman & Teng （2007)が引用
ドーン、フレデリック。ペニンクス、イールコ。ハンス・L・ボドレンダー; Fomin、Fedor V. （2005)、「平面グラフ上の効率的な正確なアルゴリズム: 球カットブランチ分解の利用」、Proc. 第 13 回欧州アルゴリズムシンポジウム (ESA ’05)、コンピュータサイエンスの講義ノート、vol. 3669、Springer-Verlag、95–106 ページ、土井: 10.1007/11561071_11、ISBN 978-3-540-29118-3
ドヴォルザーク、ズデニェク。Norin， Sergey （2016)、「Strongly sublinear separators and Polynomial Expansion」、SIAM Journal on Discrete Mathematics、30 (2): 1095–1101、arXiv : 1504.04821、doi : 10.1137/15M1017569、MR 3504982、S2C ID 27395359
デヴィッド・エップスタイン; Galil，ツヴィ; イタリアーノ、ジュゼッペ F. ; Spencer， Thomas H. (1996)、「セパレーターベースのスパース化。I. 平面性テストと最小スパニングツリー」、Journal of Computer and System Sciences、52 (1): 3–27、doi : 10.1006/jcss.1996.0002
デヴィッド・エップスタイン; Galil，ツヴィ; イタリアーノ、ジュゼッペ F. Spencer， Thomas H. (1998)、「Separator-based sparsification. II. Edge and vertex connectivity」、SIAM Journal on Computing、28 : 341、doi : 10.1137/S0097539794269072
デヴィッド・エップスタイン; ゲイリー・L・ミラー; Teng、Shang-Hua (1995)、「幾何学的セパレーターとそのアプリケーションのための決定論的線形時間アルゴリズム」、Fundamenta Informaticae、22 (4): 309–331、doi : 10.3233/FI-1995-2241
ポール・エルデシュ; ロナルド・グラハム; Szemerédi、Endre (1976)、「密な長いパスを持つ疎なグラフについて」、Computers and Mathematics with Applications (PDF)、オックスフォード: ペルガモン、pp. 365–369
ルイス、エスペレット。ジョレット、グエナエル。モーリン、パット（2020)、平面性のためのスパースユニバーサルグラフ、arXiv : 2010.05779
Fiedler、Miroslav（1973）、「代数グラフの接続性」、Czechoslovak Mathematical Journal、23（98）：298–305、DOI：10.21136/CMJ.1973.101168、HDL：10338.DMLCZ/101168、MR 0318007
フォミン、ヒョードル V. Thilikos、Dimitrios M. （2006a)、「平面グラフの分解可能性に関する新しい上限」 (PDF)、Journal of Graph Theory、51 (1): 53–81、doi : 10.1002/jgt.20121
フォミン、ヒョードル V. Thilikos、Dimitrios M. （2006b)、「平面グラフにおける支配セット: ブランチ幅と指数関数的な高速化」、SIAM Journal on Computing、36 (2): 281、doi : 10.1137/S0097539702419649、S2CID 5232238
Frederickson、Greg N. (1987)、「アプリケーションを使用した平面グラフの最短パスの高速アルゴリズム」、SIAM Journal on Computing、16 (6): 1004–1022、doi : 10.1137/0216064、MR 0917037
アラン・フリーズ; ゲイリー・L・ミラー; Teng、Shang-Hua (1992)、「計算幾何学におけるセパレーターベースの並列分割統治」、Proc. 4th ACM Symposium on Parallel Algorithms and Architecture (SPAA ’92) (PDF)、pp. 420–429、doi : 10.1145/140901.141934、ISBN 0-89791-483-X、S2CID 10914749
ガジット、ヒレル。ミラー、ゲイリー L. (1990)、「平面セパレーターとユークリッドノルム」、Proc. International Symposium on Algorithms (SIGAL’90) (PDF)、Lecture Notes in Computer Science、vol. 450、Springer-Verlag、pp. 338–347、土居：10.1007/3-540-52921-7_83、ISBN 978-3-540-52921-7
George， J. Alan (1973)、「Nested dissection of a Regular finite Element Mesh」、SIAM Journal on Numerical Analysis、10 (2): 345–363、doi : 10.1137/0710032、JSTOR 2156361
ギルバート、ジョン R. ジョアン・P・ハッチンソン; Tarjan、Robert E. (1984)、「境界属種のグラフの分離定理」、Journal of Algorithms、5 (3): 391–407、doi : 10.1016/0196-6774(84)90019-1、hdl : 1813 /6346
ギルバート、ジョン R. Tarjan、Robert E. (1986)、「ネストされた解剖アルゴリズムの分析」、Numerische Mathematik、50 (4): 377–404、doi : 10.1007/BF01396660、S2CID 122591105
Goodrich、Michael T. (1995)、「Planar separators andParallel Polygon triangulation」、Journal of Computer and System Sciences、51 (3): 374–389、doi : 10.1006/jcss.1995.1076
グレンバン、キース D. ゲイリー・L・ミラー; Teng、Shang-Hua (1997)、「慣性モーメントとグラフセパレーター」 (PDF)、Journal of Combinatorial Optimization、1 (1): 79–104、doi : 10.1023/A:1009763020645、S2CID 37829
Har-Peled、Sariel （2011)、平面セパレーターの存在の単純な証明、arXiv : 1105.0103、Bibcode : 2011arXiv1105.0103H
彼、シン。カオ・ミンヤン。Lu、Hsueh-I （2000)、「グラフの情報理論的に最適なエンコーディングのための高速一般方法論」、SIAM Journal on Computing、30 (3): 838–846、arXiv : cs/0101021、doi : 10.1137/S0097539799359117
モニカ・R・ヘンツィンガー; クライン、フィリップ。ラオ、サティシュ。Subramanian、Sairam (1997)、「平面グラフの高速最短パスアルゴリズム」、Journal of Computer and System Sciences、55 (1、パート 1): 3–23、doi : 10.1006/jcss.1997.1493、MR 1473046
ホルツァー、マーティン。シュルツ、フランク。ドロテア・ワーグナー; プラシノス、グリゴリオス。Zaroliagis、Christos （2009)、「Engineering planar separator Algorithms」、Journal of Experimental Algorithmics、14 : 1.5–1.31、doi : 10.1145/1498698.1571635、S2CID 6782855
Jordan、Camille (1869)、「Sur les assemblages des lignes」、Journal für die reine und angewandte Mathematik、70 : 185–190、ミラーらによって引用されているように。(1997)
河原林健一; ブルース、リード（2010)、「マイナー閉クラスにおける分離定理」、Proc. 第 51 回コンピュータサイエンスの基礎に関する IEEE シンポジウム、doi : 10.1109/FOCS.2010.22、S2CID 15860361
フィリップ・Ｎ・クライン；モゼス、シェイ。Weimann、Oren （2010)、「負の長さを持つ有向平面グラフの最短経路: 線形空間」 ○ ( nグ 2 n )
{ O(nlog ^{2}n)}
-time アルゴリズム」、アルゴリズムに関する ACM トランザクション、6 (2): Art. 30、18、doi : 10.1145/1721837.1721846、MR 2675697、S2CID 3095131
クライン、フィリップ。ラオ、サティシュ。ラウフ、モニカ。Subramanian、Sairam (1994)、「平面グラフの高速最短経路アルゴリズム」、Proc. 第 26 回 ACM Symposium on Theory of Computing (STOC ’94)、pp. 27–37、doi : 10.1145/195058.195092、ISBN 0-89791-663-8、S2CID 185739
ウッチキ、ヤクブ。Sankowski、Piotr （2011)、「平面グラフの最小カットと最短サイクル」 ○ ( n
ログ
ログn )
{ O(nlog log n)}
time””、Proc. 19th Annual European Symposium on Algorithms、Lecture Notes in Computer Science、vol. 6942、Springer-Verlag、pp. 155–166、arXiv : 1104.4890、doi : 10.1007/978-3-642-23719-5_14、ISBN 978-3-642-23718-8、S2CID 15152406
リチャード・J・リプトン; ローズ、ドナルド・J. Tarjan、Robert E. (1979)、「Generalizednested dissection」、SIAM Journal on Numerical Analysis、16 (2): 346–358、doi : 10.1137/0716027、JSTOR 2156840
リチャード・J・リプトン; Tarjan、Robert E. (1979)、「平面グラフの分離定理」、SIAM Journal on Applied Mathematics、36 (2): 177–189、doi : 10.1137/0136016
リチャード・J・リプトン; Tarjan、Robert E. (1980)、「Applications of a planar separator theorem」、SIAM Journal on Computing、9 (3): 615–627、doi : 10.1137/0209046、S2CID 12961628
Miller， Gary L. (1986)、「Finding small simple Cycle Separators for 2-connected planar charts」 (PDF)、Journal of Computer and System Sciences、32 (3): 265–279、doi : 10.1016/0022-0000( 86)90030-9
ゲイリー・L・ミラー; Teng，尚華市; ウィリアム・サーストン; Vavasis、Stephen A. (1997)、「球パッキングおよび最近隣グラフのセパレーター」、Journal of the ACM、44 (1): 1–29、doi : 10.1145/256292.256294、S2CID 17331739
ゲイリー・L・ミラー; Teng，尚華市; ウィリアム・サーストン; Vavasis、Stephen A. (1998)、「有限要素メッシュの幾何学的セパレーター」、SIAM Journal on Scientific Computing、19 (2): 364–386、CiteSeerX 10.1.1.307.2357、doi : 10.1137/S1064827594262613
Pach，ヤーノス; Agarwal、Pankaj K. (1995)、「Lipton–Tarjan Separator Theorem」、Combinatorial Geometry、John Wiley & Sons、99–102 ページ
パパディミトリウ，スイス連邦共和国; Sideri， M. (1996)、「グリッドグラフの二分幅」、コンピューティングシステム理論、29 (2): 97–110、doi : 10.1007/BF01305310、S2CID 15617963
プロトキン、セルジュ。ラオ、サティシュ。Smith、Warren D. (1994)、「浅い除外マイナーと改善されたグラフ分解」、Proc. 第 5 回離散アルゴリズムに関する ACM-SIAM シンポジウム (SODA ’94)、pp. 462–470、ISBN 9780898713299
ブルース・リード; Wood、David R. （2009)、「マイナーを除くグラフ内の区切り文字を見つける線形時間アルゴリズム」、ACM Transactions on Algorithms、5 (4): 1–16、doi : 10.1145/1597036.1597043、S2CID 760001
ポール・D・シーモア; Thomas、Robin (1994)、「コールルーティングとラットキャッチャー」、Combinatorica、14 (2): 217–241、doi : 10.1007/BF01215352、S2CID 7508434
ウォーレン・D・スミス; Wormald、Nicholas C. (1998)、「幾何学的分離定理と応用」、第 39 回コンピュータサイエンスの基礎に関する年次シンポジウム (FOCS ’98)、1998 年 11 月 8 ～ 11 日、米国カリフォルニア州パロアルト、 IEEE Computer Society、pp .232–243、土井: 10.1109/SFCS.1998.743449、S2CID 17962961
ダニエル・A・スピルマン; Teng、Shang-Hua (1996)、「ディスクパッキングと平面セパレーター」、Proc. 12th ACM Symposium on Computational Geometry (SCG ’96) (PDF)、pp. 349–358、doi : 10.1145/237218.237404、ISBN 0-89791-804-5、S2CID 15937001
ダニエル・A・スピルマン; Teng、Shang-Hua （2007)、「スペクトル分割作品: 平面グラフと有限要素メッシュ」、線形代数とその応用、421 (2–3): 284–305、doi : 10.1016/j.laa.2006.07.020
シコラ、オンドレイ。Vrt’o、Imrich (1993)、「アプリケーションを使用した有界属グラフのエッジセパレーター」、Theoretical Computer Science、112 (2): 419–429、doi : 10.1016/0304-3975(93)90031-N
タザリ、シアマック。Müller-Hannemann、Matthias （2009)、「マイナー閉グラフクラス上の線形時間の最短経路、シュタイナーツリー近似への適用」、離散応用数学、157 (4): 673–684 、 doi : 10.1016 / j 。ダム.2008.08.002
Ungar、Peter (1951)、「平面グラフに関する定理」、Journal of the London Mathematical Society、1 (4): 256、doi : 10.1112/jlms/s1-26.4.256
ワイマン、オーレン。Yuster、Raphael （2010)、「平面グラフの周囲長の計算」 ○ ( n
ログn )
{ O(nlog n)}
時間」、離散数学に関する SIAM ジャーナル、24 (2): 609、CiteSeerX 10.1.1.156.5730、doi : 10.1137/090767868
Wulff-Nilsen、Christian （2009)、実エッジ重みを含む平面有向グラフの周囲長 ○ ( n
ログ3 n )
{ O(nlog ^{3}n)}

時間、arXiv : 0908.0697、Bibcode : 2009arXiv0908.0697W”