SPQRツリー

グラフ理論は数学の一分野であり、二連結グラフの三連結成分は、グラフ内のすべての 2 頂点カットを記述するより小さなグラフのシステムです。SPQRツリーは、コンピュータサイエンス、特にグラフアルゴリズムで使用されるツリー データ構造であり、グラフの三連結成分を表します。グラフの SPQR ツリーは線形時間で構築でき^{[ 1 ]} 、動的グラフアルゴリズムやグラフ描画にいくつかの応用があります。

SPQR ツリーの基本的な構造、グラフの 3 連結成分、およびこの分解と平面グラフの平面埋め込みとの間の関係は、最初にSaunders Mac Lane ( 1937 )によって調査されました。これらの構造は、 Di BattistaとTamassia ( 1989 、1990 、1996 )によって SPQR ツリーとして形式化される前に、他のいくつかの研究者^{[ 2 ]}によって効率的なアルゴリズムで使用されました。  

SPQRツリーは、各ノードxに対して無向グラフまたは多重グラフG _xが関連付けられる根なしツリーの形式をとります。ノードおよびそれに関連付けられたグラフは、SPQRという頭文字で示される4つのタイプのいずれかになります。

• Sノードでは、関連付けられたグラフは3つ以上の頂点とエッジを持つサイクルグラフです。このケースは、直並列グラフにおける直列合成に類似しています。Sは「直列」を意味します。^{[ 3 ]}
• Pノードでは、関連するグラフは双極子グラフ、つまり2つの頂点と3つ以上の辺を持つ多重グラフであり、サイクルグラフの平面双対です。このケースは、直列並列グラフの並列合成に類似しています。Pは「並列」を意味します。^{[ 3 ]}
• Qノードでは、関連付けられたグラフには実エッジが1つだけ存在します。この自明なケースは、エッジが1つしかないグラフを扱うために必要です。SPQRツリーに関するいくつかの研究では、このタイプのノードは複数のエッジを持つグラフのSPQRツリーには現れません。また、他の研究では、すべての非仮想エッジは1つの実エッジと1つの仮想エッジを持つQノードで表現する必要があり、他のノードタイプのエッジはすべて仮想でなければなりません。
• Rノードでは、関連付けられたグラフはサイクルや双極子ではない3連結グラフです。Rは「rigid」の略です。平面グラフ埋め込みにおけるSPQRツリーの適用では、Rノードの関連付けられたグラフは一意の平面埋め込みを持ちます。^{[ 3 ]}

SPQRツリーの2つのノード間の各エッジxyには、2つ_の有向仮想エッジが関連付けられています。そのうちの1つはGxのエッジであり、もう1つはGyのエッジです。グラフGxの各エッジは、最大_で1つのSPQRツリーエッジの仮想エッジとなることができます_。

SPQR ツリーTは、次のように形成される2 連結グラフG _Tを表します。SPQR ツリーのエッジxy がG _xの仮想エッジabとG _yの仮想エッジcdを関連付ける場合、aとcを 1 つのスーパー頂点にマージし、bとd を別のスーパー頂点にマージし、2 つの仮想エッジを削除して、より大きな単一のグラフを形成します。つまり、より大きなグラフはG _xとG _yの2-クリーク和です。SPQR ツリーの各エッジに対してこの接着ステップを実行すると、グラフG _Tが生成されます。接着ステップを実行する順序は結果に影響しません。グラフG _xのいずれかの各頂点は、このようにして、マージされたスーパー頂点であるG _Tの一意の頂点と関連付けられます。

通常、SPQRツリー内では、2つのSノードが隣接したり、2つのPノードが隣接したりすることは許されません。なぜなら、そのような隣接が発生すると、2つのノードが1つのより大きなノードにマージされてしまう可能性があるからです。この仮定の下で、SPQRツリーはそのグラフから一意に決定されます。グラフGが、隣接するPノードも隣接するSノードもないSPQRツリーで表される場合、SPQRツリーのノードに関連付けられたグラフG _xは、 Gの3連結成分として知られています。

与えられた2頂点連結グラフのSPQR木は線形時間で構築できる。^{[ 1 ]}

グラフの三連結成分を構築する問題は、Hopcroft & Tarjan (1973)によって初めて線形時間で解決されました。このアルゴリズムに基づいて、Di Battista & Tamassia (1996) は、成分のリストだけでなく、完全な SPQR ツリー構造も線形時間で構築できるはずだと提案しました。GDToolkit ライブラリの一部として、SPQR ツリーのより遅いアルゴリズムの実装が提供された後、Gutwenger & Mutzel (2001)が最初の線形時間実装を提供しました。このアルゴリズムの実装プロセスの一環として、彼らはHopcroft & Tarjan (1973)の以前の研究のいくつかのエラーも修正しました。

Gutwenger & Mutzel (2001)のアルゴリズムは、以下の全体的な手順を含んでいます。

1. グラフのエッジを、エンドポイントの数値インデックスのペアに基づいてソートします。この際、各エンドポイントに対してバケットソートを2回行う基数ソートの変種を使用します。このソート処理の後、同じ2つの頂点間の平行エッジはソート済みリスト内で隣接し、最終的なSPQRツリーのPノードに分割できるため、残りのグラフは単純なものになります。
2. グラフを分割コンポーネントに分割します。これは、分離頂点のペアを見つけ、その2つの頂点でグラフを2つの小さなグラフに分割し（分離頂点を端点とする仮想エッジのペアで連結）、分離ペアがなくなるまでこの分割プロセスを繰り返すことによって形成されるグラフです。このようにして見つかった分割は一意に定義されません。なぜなら、SPQRツリーのSノードとなるべきグラフの部分が複数の三角形に細分化されるからです。
3. 各分割コンポーネントに、P（複数のエッジを持つ2頂点の分割コンポーネント）、S（三角形の形状をした分割コンポーネント）、またはR（その他の分割コンポーネント）のラベルを付けます。リンクされた仮想エッジのペアを共有する2つの分割コンポーネントが存在し、両方のコンポーネントがタイプSであるか、両方のコンポーネントがタイプPである場合は、それらを同じタイプの1つの大きなコンポーネントにマージします。

分割されたコンポーネントを見つけるために、Gutwenger & Mutzel (2001)は深さ優先探索を使用して、彼らが「パームツリー」と呼ぶ構造を見つけます。これは、深さ優先探索ツリーであり、ツリーに属するエッジはツリーのルートから離れる方向に、その他のすべてのエッジはルートに向かって方向付けられています。次に、ツリー内のノードの特別な先行順番号付けを見つけ、この番号付けの特定のパターンを使用して、グラフをより小さなコンポーネントに分割できる頂点のペアを特定します。このようにしてコンポーネントが見つかると、スタックデータ構造を使用して、新しいコンポーネントの一部となるべきエッジを特定します。

• ブロックカットツリーは、2頂点連結成分の類似したツリー構造である。
• ゴモリー・フー木は、グラフのエッジ接続性を特徴付ける別の木構造である。
• ツリー分解、より大きなカットへの一般化（もはや一意ではない）

• Bienstock, Daniel; Monma, Clyde L. (1988)、「平面グラフにおける頂点を面によって覆うことの複雑性について」、SIAM Journal on Computing、17 (1): 53–76、CiteSeerX 10.1.1.542.2314、doi : 10.1137/0217004 。
• Di Battista, Giuseppe; Tamassia, Roberto (1989)、「インクリメンタル平面性テスト」、第30回コンピュータサイエンス基礎に関する年次シンポジウム議事録、pp. 436–441、doi : 10.1109/SFCS.1989.63515、ISBN  0-8186-1982-1。
• Di Battista, Giuseppe; Tamassia, Roberto (1990)、「SPQR木を用いたオンライングラフアルゴリズム」、第17回国際オートマタ・言語・プログラミングコロキウム議事録、Lecture Notes in Computer Science、第 443巻、Springer-Verlag、pp. 598–611、doi : 10.1007/BFb0032061、ISBN  978-3-540-52826-5。
• Di Battista, Giuseppe; Tamassia, Roberto (1996)、「オンライン平面性テスト」(PDF)、SIAM Journal on Computing、25 (5): 956–997、doi : 10.1137/S0097539794280736。
• Gutwenger, Carsten; Mutzel, Petra (2001)、「SPQRツリーの線形時間実装」、第8回国際グラフ描画シンポジウム（GD 2000）論文集、Lecture Notes in Computer Science、第1984巻 、Springer-Verlag、77–90ページ、 doi : 10.1007 /3-540-44541-2_8、ISBN  978-3-540-41554-1。
• Hopcroft, John ; Tarjan, Robert (1973)、「グラフを3連結成分に分割する」、SIAM Journal on Computing、2 (3): 135–158、doi : 10.1137/0202012、hdl : 1813/6037。
• Mac Lane, Saunders (1937)、「平面組合せグラフの構造的特徴付け」、Duke Mathematical Journal、3 (3): 460–472、doi : 10.1215/S0012-7094-37-00336-3。

• Open Graph Drawing FrameworkにおけるSPQRツリーの実装。
• jBPTライブラリにおける三連結成分のツリーのJava実装（TCTreeクラスを参照）。