拓撲圖論
此條目介紹的是圖嵌入的研究。關於平面上有交叉的圖，請見「拓撲圖」。拓撲圖論是圖論的一個分支，研究曲面中的圖嵌入、圖的空間嵌入及作為拓撲空間的圖，[1]還研究圖的浸入。
將圖嵌入曲面意味著在曲面（如球面）上繪製圖，而不使兩條邊相交。常作為數學謎題的基本嵌入問題是三間小屋問題，其他應用如印刷電子電路，即在電路板（面）上印刷（嵌入）電路（圖），且不短路。
作為拓撲空間的圖
對無向圖，可將抽象單純復形C與每個頂點的單元素集同每個邊的2元素集聯繫起來。復形的幾何實現|C|由每條邊的單位區間[0,1]的副本組成，這些區間的端點在頂點處粘合在一起。這樣來看，將圖嵌入曲面或作為其他圖的細分都是拓撲嵌入的實例，圖同胚只是拓撲同胚的特例，連通圖的概念與拓撲連通重合，並且若且唯若連通圖的基本群平凡時，才是樹。
與圖相關的其他單純復形還有團復形 （以圖的每個團為集合）與匹配復形（以圖的每個匹配為集合）（等同於線圖補集的團復形） 。完全二分圖的匹配復形稱作棋盤復形，因為其也可描述為棋盤上非攻擊車集合的復形。[2]
實例研究
約翰·霍普克洛夫特和羅伯特·塔揚[3]提出了一種圖的平面性檢驗的方法，且用時與邊數成線性關係。他們的算法通過構建圖嵌入（他們稱作「棕櫚樹」）實現。高效的平面性檢驗是圖形繪製的基礎。
金芳蓉等人[4]研究了書嵌入問題，圖的頂點沿書脊排列，圖的邊分別繪製在不同頁上，使同一頁的邊不交叉。這個問題抽象了多層印刷電路板布線問題。
另見
參考
- ^ Gross, J.L.; Tucker, T.W. Topological graph theory. Dover. 2012 [1987] [2024-01-19]. ISBN 978-0-486-41741-7. （原始內容存檔於2022-09-30）.
- ^ Shareshian, John; Wachs, Michelle L. Torsion in the matching complex and chessboard complex. Advances in Mathematics. 2007, 212 (2): 525–570 [2004]. CiteSeerX 10.1.1.499.1516
. arXiv:math.CO/0409054 . doi:10.1016/j.aim.2006.10.014 .
- ^ Hopcroft, John; Tarjan, Robert E. Efficient Planarity Testing (PDF). Journal of the ACM. 1974, 21 (4): 549–568. S2CID 6279825. doi:10.1145/321850.321852. hdl:1813/6011 .
- ^ Chung, F. R. K.; Leighton, F. T.; Rosenberg, A. L. Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design (PDF). SIAM Journal on Algebraic and Discrete Methods. 1987, 8 (1): 33–58 [2023-12-02]. doi:10.1137/0608002. （原始內容存檔 (PDF)於2017-09-21）.
