平面性試験

グラフ理論において、平面性テスト問題は、与えられたグラフが平面グラフであるかどうか（つまり、平面上に辺の交差なしに描画できるかどうか）をテストするアルゴリズムの問​​題である。これはコンピュータサイエンスにおいてよく研究されている問題であり、多くの実用的なアルゴリズムが登場しており、その多くは新しいデータ構造を活用している。これらの方法のほとんどはO ( n ) 時間（線形時間）で動作する。ここでnはグラフの辺（または頂点）の数であり、漸近的に最適である。平面性テストアルゴリズムの出力は、単一のブール値ではなく、グラフが平面である場合は平面グラフ埋め込み、そうでない場合はクラトフスキー部分グラフなどの平面性に対する障害となる場合がある。

平面性基準

平面性検定アルゴリズムは、通常、グラフの描画とは独立に平面グラフの集合を特徴付けるグラフ理論の定理を利用する。これには以下が含まれる。

Fraysseix–Rosenstiehl の平面性基準は、平面性テストのアルゴリズムの一部として直接使用できますが、Kuratowski の定理と Wagner の定理には間接的な応用があります。アルゴリズムが特定のグラフ内でK 5またはK 3,3のコピーを見つけることができる場合、入力グラフが平面ではないことが保証され、追加の計算なしで返すことができます。

平面グラフを数学的に特徴付けるが、平面性テスト アルゴリズムの中心ではないその他の平面性基準には、次のものがあります。

アルゴリズム

パス追加方法

ホップクロフトとタージャン[ 1 ]の古典的なパス追加法は、1974年に初めて公開された線形時間平面性テストアルゴリズムでした。ホップクロフトとタージャンのアルゴリズムの実装は、メルホーン、ムッツェル、ネアーによる効率的なデータ型とアルゴリズムのライブラリで提供されています。[ 2 ] [ 3 ] [ 4 ] 2012年にテイラー[ 5 ]はこのアルゴリズムを拡張して、二重連結成分の平面埋め込みの巡回エッジ順序のすべての順列を生成しました。

頂点追加法

頂点追加法は、与えられたグラフの誘導サブグラフの可能な埋め込みを表すデータ構造を維持し、このデータ構造に頂点を1つずつ追加することで機能します。これらの方法は、 1967年にLempel、Even、 Cederbaumによって考案された非効率的な O( n 2 ) 方法から始まりました。 [ 6 ]これは、 s、t番号付けステップに線形時間のソリューションを見つけた Even と Tarjan によって改良され、[ 7 ]またBoothとLuekerによってPQ ツリーデータ構造が開発されました。これらの改良により、線形時間となり、実際にはパス追加法よりも優れたパフォーマンスを発揮します。[ 8 ]この方法は、平面グラフの平面埋め込み (描画) を効率的に計算できるようにも拡張されました。[ 9 ] 1999年にShihとHsuはPC木（PQ木の非根付き変種）と頂点の深さ優先探索木の後方順序走査を使用してこれらの手法を簡素化した。 [ 10 ]

エッジ追加法

2004 年に、John Boyer とWendy Myrvold [ 11 ]は、元々 PQ ツリー法にヒントを得た、簡略化された O( n ) アルゴリズムを開発した。このアルゴリズムは PQ ツリーを削除し、可能であればエッジ追加を使用して平面埋め込みを計算する。そうでない場合は、Kuratowski サブディビジョン ( K 5またはK 3,3のいずれか) を計算する。これは、今日の 2 つの最先端アルゴリズムのうちの 1 つである (もう 1 つは de Fraysseix、Ossona de Mendez、および Rosenstiehl [ 12 ] [ 13 ]の平面性テスト アルゴリズム)。Boyer と Myrvold の平面性テストの初期バージョンとの実験的な比較については、 [ 14 ]を参照されたい。さらに、Boyer–Myrvold テストは、出力サイズに線形に依存する実行時間で、非平面入力グラフの複数の Kratowski サブディビジョンを抽出できるように拡張された。[ 15 ]平面性テスト[ 16 ] [ 17 ]と多重クラトフスキー部分グラフの抽出[ 16 ]のソースコードは公開されています。クラトフスキー部分グラフを頂点単位で線形時間で特定するアルゴリズムは、1980年代にウィリアムソンによって開発されました。[ 18 ]

施工順序法

別の方法では、3連結グラフの帰納的構築を使用して、 Gのすべての3連結コンポーネントの平面埋め込み（したがって、G自体の平面埋め込み）を段階的に構築します。[ 19 ]構築はK 4から始まり、完全なコンポーネントまでの途中のすべての中間グラフが再び3連結になるように定義されます。このようなグラフは一意の埋め込み（反転と外面の選択まで）を持つため、次の大きなグラフは、まだ平面である場合、前のグラフを改良したものでなければなりません。これにより、平面性テストを、各ステップで次に追加されるエッジの両端が現在の埋め込みの外面にあるかどうかをテストするだけで済みます。これは概念的には非常に単純（かつ線形実行時間）ですが、方法自体は構築シーケンスを見つける複雑さに悩まされています。

動的アルゴリズム

平面性テストは動的アルゴリズムモデルで研究されており、このモデルでは、グラフが典型的にはエッジの挿入/削除の形でローカル更新を受ける際に、問題（この場合は平面性）に対する解答が維持される。エッジ到着の場合、La Poutré による漸近的にタイトな逆アッカーマン関数更新時間アルゴリズム [ 20 ] があり、これはDi Battista、Tamassia 、およびWestbrookによるアルゴリズムを改良したものである[ 21 ] [ 22 ] [ 23 ] 。エッジが挿入および削除される完全に動的なケースでは、 PătrașcuおよびDemaineによる対数更新時間下限[ 24 ]とHolmおよびRotenbergによる多重対数更新時間アルゴリズム[ 25 ] があり、これはEppstein、Galil、Italiano 、Sarnak、および Spencerによる部分線形更新時間アルゴリズムを改良したものである[ 26 ]。[ 26 ] [ 27 ]

参考文献

  1. ^ホップクロフト、ジョン;タージャン、ロバート E. (1974)、「効率的な平面性テスト」、Journal of the Association for Computing Machinery、21 (4): 549– 568、doi : 10.1145/321850.321852、hdl : 1813/ 6011 、S2CID  6279825。
  2. ^ Mehlhorn, Kurt ; Mutzel, Petra (1996)、「HopcroftとTarjanの平面性テストアルゴリズムの埋め込みフェーズについて」(PDF)、Algorithmica、16 (2): 233– 242、doi : 10.1007/bf01940648、hdl : 11858/00-001M-0000-0014-B51D-B、S2CID 10014462 
  3. ^ Mehlhorn, Kurt ; Mutzel, Petra ; Näher, Stefan (1993)、ホップクロフトとタージャンの平面性テストと埋め込みアルゴリズムの実装
  4. ^ Mehlhorn, Kurt ; Näher, Stefan (1995)、「LEDA: 効率的なデータ型とアルゴリズムのライブラリ」、Communications of the ACM、38 (1): 96– 102、CiteSeerX 10.1.1.54.9556、doi : 10.1145/204865.204889、S2CID 2560175  
  5. ^ Taylor, Martyn G. (2012).パス追加による平面性テスト（Ph.D.）. ケント大学. 2016年3月5日時点のオリジナルよりアーカイブ。代替URL
  6. ^ Lempel, A. ; Even, S. ; Cederbaum, I. (1967)、「グラフの平面性テストのためのアルゴリズム」、Rosenstiehl, P. (編)、『グラフ理論』、ニューヨーク：Gordon and Breach、pp.  215– 232。
  7. ^ Even, Shimon ; Tarjan, Robert E. (1976)、「st -numberingの計算」、理論計算機科学、2 (3): 339– 344、doi : 10.1016/0304-3975(76)90086-4。
  8. ^ Boyer & Myrvold (2004)、p. 243：「LEDAでの実装は、他の多くのO( n )時間平面性アルゴリズムのLEDA実装よりも遅いです。」
  9. ^千葉 暢;西関 剛; 阿部 明; 小澤 毅 (1985)「PQ木を用いた平面グラフ埋め込みのための線形アルゴリズム」, Journal of Computer and System Sciences , 30 (1): 54– 76, doi : 10.1016/0022-0000(85)90004-2。
  10. ^ Shih, WK; Hsu, WL (1999)、「新しい平面性テスト」、理論計算機科学、223 ( 1–2 ): 179– 191、doi : 10.1016/S0304-3975(98)00120-0。
  11. ^ Boyer, John M.; Myrvold, Wendy J. (2004)、「最先端のエッジ：エッジ追加による簡素化されたO( n )平面性」 （PDF）、Journal of Graph Algorithms and Applications、8 (3): 241– 273、doi : 10.7155/jgaa.00091。
  12. ^ de Fraysseix, H.; Ossona de Mendez, P.; Rosenstiehl , P. (2006)、「トレモー木と平面性」、International Journal of Foundations of Computer Science、17 (5): 1017– 1030、arXiv : math/0610935、Bibcode : 2006math.....10935D、doi : 10.1142/S0129054106004248、S2CID 40107560 。
  13. ^ Brandes, Ulrik (2009),左右平面性テスト(PDF)。
  14. ^ Boyer, John M.; Cortese, PF; Patrignani, M.; Battista, GD (2003)、「Stop minding your P's and Q's: implement a fast and simple DFS-based planarity testing and embedding algorithm」、Proc. 11th Int. Symp. Graph Drawing (GD '03)、Lecture Notes in Computer Science、vol. 2912、Springer-Verlag、pp.  25– 36
  15. ^ Chimani, M.; Mutzel, P .; Schmidt, JM (2008). 「複数のKuratowski細分区間の効率的な抽出」Proc. 15th Int. Symp. Graph Drawing (GD'07) . Lecture Notes in Computer Science. Vol. 4875. シドニー, オーストラリア: Springer-Verlag. pp.  159– 170. doi : 10.1007/978-3-540-77537-9_17 . ISBN 978-3-540-77536-2。。
  16. ^ a b「OGDF - オープングラフ描画フレームワーク: スタート」。
  17. ^ 「Boost グラフ ライブラリ: Boyer-Myrvold 平面性テスト/埋め込み - 1.40.0」。
  18. ^ Williamson, SG (1984)、「深さ優先探索とクラトフスキー部分グラフ」、Journal of the ACM、31 (4): 681– 693、doi : 10.1145/1634.322451、S2CID 8348222 
  19. ^ Schmidt, Jens M. (2014)、「The Mondshein Sequence」、オートマトン、言語、プログラミング; 第41回国際オートマトン、言語、プログラミングコロキウム (ICALP'14) の議事録、コンピュータサイエンスの講義ノート、第8572巻、pp.  967– 978、doi : 10.1007/978-3-662-43948-7_80、ISBN 978-3-662-43947-0
  20. ^ La Poutré, Johannes A. (1994)、「増分平面性テストのためのアルファアルゴリズム」、第26回ACMコンピューティング理論シンポジウム(STOC)の議事録、pp.  706– 715、doi : 10.1145/195058.195439、S2CID 16799743 
  21. ^ Di Battista, Giuseppe; Tamassia, Roberto (1996)、「SPQR木による三連結成分のオンラインメンテナンス」、Algorithmica、15 (4): 302– 318、doi : 10.1007/BF01961541、S2CID 7838334 
  22. ^ Tamassia, Roberto (1996)、「オンライン平面グラフ埋め込み」、Journal of Algorithms、21 (2): 201– 239、doi : 10.1006/jagm.1996.0044
  23. ^ Westbrook, Jeffery (1992)、「高速増分平面性テスト」、オートマタ、言語、プログラミング、第19回国際コロキウム、ICALP92、コンピュータサイエンスの講義ノート、第623巻、pp.  342– 353、doi : 10.1007/3-540-55719-9_86、ISBN 978-3-540-55719-7
  24. ^ Pătrașcu, Mihai ; Demaine, Erik (2004)、「動的接続性の下限値」、第14回ACM-SIAM離散アルゴリズムシンポジウム論文集、pp.  546– 553、doi : 10.1145/1007352.1007435、ISBN 1581138520、S2CID  2121130
  25. ^ Holm, Jacob; Rotenberg, Eva (2020). 「対数時間で完全動的平面性テスト」. Makarychev, Konstantin; Makarychev, Yury; Tulsiani, Madhur; Kamath, Gautam; Chuzhoy, Julia (編). Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020 . Association for Computing Machinery. pp.  167– 180. arXiv : 1911.03449 . doi : 10.1145/3357713.3384249 . ISBN 978-1-4503-6979-4。
  26. ^ Eppstein, David; Galil, Zvi; Italiano, Giuseppe; Spencer, Thomas (1996)、「セパレータベースのスパース化：I. 平面性テストと最小全域木」、Journal of Computer and System Sciences、doi : 10.1006/jcss.1996.0002
  27. ^ Galil, Zvi; Italiano, Giuseppe; Sarnak, Neil (1999)「完全動的平面性テストとその応用」Journal of the ACM , 46 : 28–91 , doi : 10.1145/300515.300517 , S2CID 7009330 
「 https://en.wikipedia.org/w/index.php?title=Planarity_testing&oldid=1336627782」より取得