位相グラフ理論

パップスグラフと関連マップのトーラスへの埋め込みを詳細に示すアニメーション

数学において、位相グラフ理論はグラフ理論の一分野である。グラフの表面への埋め込み、グラフの空間的埋め込み、位相空間としてのグラフを研究する。^[1]また、グラフの浸漬も研究する。

グラフを表面に埋め込むということは、2 つの辺が交差することなく、グラフを表面 (たとえば球面) 上に描画することを意味します。数学的なパズルとしてよく提示される基本的な埋め込み問題は、 3 つの効用問題です。その他の応用としては、電子回路の印刷が挙げられます。その目的は、2 つの接続が交差して短絡が生じることなく、回路 (グラフ) を回路基板(表面)に印刷 (埋め込む) することです。

位相空間としてのグラフ

無向グラフには、頂点ごとに 1 つの要素の集合と、辺ごとに 2 つの要素の集合を持つ抽象単体複体 C を関連付けることができます。複体の幾何学的実現 | C | は、辺ごとに単位区間[0,1]のコピーで構成され、これらの区間の端点は頂点で互いに接着されます。この見方では、グラフの表面への埋め込みや他のグラフの細分化はどちらも位相的埋め込みの例であり、グラフの同相は位相的同相の特殊化にすぎず、連結グラフの概念は位相的連結性と一致し、連結グラフが木であるためには、その基本群が自明である必要があります。

グラフに関連するその他の単体複合体には、グラフのクリークごとに集合を持つホイットニー複合体またはクリーク複合体、およびグラフのマッチングごとに集合を持つマッチング複合体（線グラフの補集合のクリーク複合体と同等）がある。完全二部グラフのマッチング複合体はチェスボード複合体と呼ばれ、チェス盤上の攻撃しないルークの集合の複合体としても説明できる。^[2]

研究例

ジョン・ホップクロフトとロバート・タージャン^{[3]は、グラフの}平面性を辺の数に比例した時間でテストする手段を導き出しました。彼らのアルゴリズムは、グラフ埋め込みを構築することでこれを行います。彼らはこれを「ヤシの木」と呼んでいます。効率的な平面性テストはグラフ描画の基本です。

Fan Chungら^{[4]は、グラフの頂点が本の背表紙に沿って一直線に並ぶように}グラフを本に埋め込む問題を研究した。グラフの辺は、同じページにある辺が交差しないように別々のページに描かれている。この問題は、多層プリント基板の配線で生じるレイアウト問題を抽象化している。

グラフ埋め込みは、グラフマイナー理論とグラフ構造定理を介して、グラフに関する構造的結果を証明するためにも使用されます。

参照

注記

^ Gross, JL; Tucker, TW (2012) [1987]. トポロジカルグラフ理論. ドーバー. ISBN 978-0-486-41741-7。
^ Shareshian, John; Wachs, Michelle L. (2007) [2004]. 「マッチング複合体とチェスボード複合体のねじれ」. Advances in Mathematics . 212 (2): 525–570. arXiv : math.CO/0409054 . CiteSeerX 10.1.1.499.1516 . doi : 10.1016/j.aim.2006.10.014 .
^ Hopcroft, John ; Tarjan, Robert E. (1974). 「効率的な平面性テスト」(PDF) . Journal of the ACM . 21 (4): 549–568. doi :10.1145/321850.321852. hdl : 1813/6011 . S2CID 6279825.
^ Chung, FRK ; Leighton, FT ; Rosenberg, AL (1987). 「本へのグラフの埋め込み: VLSI 設計への応用に関するレイアウト問題」(PDF) . SIAM Journal on Algebraic and Discrete Methods . 8 (1): 33–58. doi :10.1137/0608002.

[1] Gross, JL; Tucker, TW (2012) [1987]. トポロジカルグラフ理論. ドーバー. ISBN 978-0-486-41741-7。

[2] Shareshian, John; Wachs, Michelle L. (2007) [2004]. 「マッチング複合体とチェスボード複合体のねじれ」. Advances in Mathematics . 212 (2): 525–570. arXiv : math.CO/0409054 . CiteSeerX 10.1.1.499.1516 . doi : 10.1016/j.aim.2006.10.014 .

[3] Hopcroft, John ; Tarjan, Robert E. (1974). 「効率的な平面性テスト」(PDF) . Journal of the ACM . 21 (4): 549–568. doi :10.1145/321850.321852. hdl : 1813/6011 . S2CID 6279825.

[4] Chung, FRK ; Leighton, FT ; Rosenberg, AL (1987). 「本へのグラフの埋め込み: VLSI 設計への応用に関するレイアウト問題」(PDF) . SIAM Journal on Algebraic and Discrete Methods . 8 (1): 33–58. doi :10.1137/0608002.