SPQR ツリー

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

SPQRツリーの基礎となる基本構造、グラフの三連結成分、およびこの分解と平面グラフの平面埋め込みとの関係は、サンダース・マック・レーン（1937）によって初めて研究されました。これらの構造は、ディ・バティスタとタマシア（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 つはG _xのエッジであり、もう 1 つはG _yのエッジです。グラフG _xの各エッジは、最大で 1 つの SPQR ツリー エッジの仮想エッジになることができます。

SPQR ツリーT は、次のように形成された2 接続グラフG _Tを表します。SPQR ツリーのエッジxy がG _xの仮想エッジab をG _yの仮想エッジcdに関連付けるたびに、aとcを 1 つのスーパー頂点にマージし、bとd を別の 1 つのスーパー頂点にマージし、2 つの仮想エッジを削除して、1 つの大きなグラフを形成します。つまり、大きなグラフは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]

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

Gutwenger & Mutzel (2001) のアルゴリズムには、次の全体的なステップが含まれます。

1. グラフのエッジを、エンドポイントの数値インデックスのペアでソートします。これには、エンドポイントごとに 1 回ずつ、バケット ソートを 2 回実行する基数ソートのバリエーションを使用します。このソート手順の後、同じ 2 つの頂点間の平行エッジはソートされたリスト内で互いに隣接し、最終的な SPQR ツリーの P ノードに分割できるため、残りのグラフはシンプルになります。
2. グラフを分割コンポーネントに分割します。分割コンポーネントは、分離する頂点のペアを見つけ、この 2 つの頂点でグラフを 2 つの小さなグラフに分割し (分離する頂点をエンドポイントとする仮想エッジのリンク ペアを使用)、分離ペアがなくなるまでこの分割プロセスを繰り返すことで形成できるグラフです。この方法で見つかったパーティションは一意に定義されません。これは、SPQR ツリーの S ノードになるグラフの部分が複数の三角形に分割されるためです。
3. 各分割コンポーネントに、P (複数のエッジを持つ 2 つの頂点の分割コンポーネント)、S (三角形の分割コンポーネント)、または R (その他の分割コンポーネント) のラベルを付けます。リンクされた仮想エッジのペアを共有する 2 つの分割コンポーネントが存在し、両方のコンポーネントのタイプが S であるか、両方ともタイプが P である場合は、それらを同じタイプの 1 つの大きなコンポーネントにマージします。

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

グラフG (Q ノードなし)の SPQR ツリーを使用すると、Gからuとv を削除すると切断されたグラフと、残りのグラフの接続コンポーネントが残るような、 G内の頂点uとvのすべてのペアを簡単に見つけることができます。

• 2 つの頂点uとv は、R ノードに関連付けられたグラフ内の仮想エッジの 2 つのエンドポイントである可能性があり、その場合、2 つのコンポーネントは、対応する SPQR ツリー エッジを削除することによって形成された SPQR ツリーの 2 つのサブツリーによって表されます。
• 2 つの頂点uとv は、 2 つ以上の仮想エッジを持つ P ノードに関連付けられたグラフ内の 2 つの頂点である可能性があります。この場合、 uとvを削除して形成されたコンポーネントは、ノード内の各仮想エッジごとに 1 つずつ、SPQR ツリーのサブツリーによって表されます。
• 2 つの頂点uとv は、グラフ内の S ノードに関連付けられた 2 つの頂点である可能性がありますが、uとv は隣接していないか、エッジuvが仮想です。エッジが仮想の場合、ペア ( u、v ) もタイプ P および R のノードに属し、コンポーネントは上記のとおりです。2 つの頂点が隣接していない場合、2 つのコンポーネントは、S ノードに関連付けられたサイクル グラフの 2 つのパスと、それらの 2 つのパスに接続された SPQR ツリー ノードによって表されます。

平面グラフが 3 連結の場合、どの面を外面とするか、および埋め込みの向きを選択するまで、平面埋め込みは一意である。埋め込みの面は、グラフの非分離サイクルとまったく同じである。しかし、2 連結だが 3 連結ではない平面グラフ (ラベル付き頂点と辺を持つ) の場合、平面埋め込みを見つける自由度が高くなる可能性がある。具体的には、グラフの SPQR ツリー内の 2 つのノードが仮想辺のペアで接続されているときはいつでも、一方のノードの向きをもう一方のノードに対して反転 (その鏡像に置き換える) することが可能である。さらに、SPQR ツリーの P ノードでは、P ノードの仮想辺に接続されているグラフのさまざまな部分を任意に並べ替えることができる。すべての平面表現は、このように記述できる。^[4]

• ブロックカットツリー、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)、「増分平面性テスト」、Proc. 30th Annual Symposium on Foundations of Computer Science、pp. 436–441、doi :10.1109/SFCS.1989.63515、ISBN 0-8186-1982-1。
• Di Battista, Giuseppe; Tamassia, Roberto (1990)、「SPQR ツリーを使用したオンライン グラフ アルゴリズム」、Proc. 17th International Colloquium on Automata, Languages and Programming、Lecture Notes in Computer Science、vol. 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 ツリーの線形時間実装」、Proc. 8th International Symposium on Graph Drawing (GD 2000)、Lecture Notes in Computer Science、vol. 1984、Springer-Verlag、pp. 77–90、doi : 10.1007/3-540-44541-2_8、ISBN 978-3-540-41554-1。
• ホップクロフト、ジョン;タージャン、ロバート(1973)、「グラフを三連結コンポーネントに分割する」、SIAM Journal on Computing、2 (3): 135–158、doi :10.1137/0202012、hdl : 1813/6037。
• マックレーン、サンダース（1937）、「平面組合せグラフの構造的特徴付け」、デューク数学ジャーナル、3（3）：460–472、doi：10.1215 / S0012-7094-37-00336-3。

• Open Graph Drawing Framework での SPQR ツリーの実装。
• jBPT ライブラリ内の 3 連結コンポーネントのツリー Java 実装 (TCTree クラスを参照)。