此條目介紹的是圖嵌入的研究。關於平面上有交叉的圖，請見「拓撲圖」。拓撲圖論是圖論的一個分支，研究曲面中的圖嵌入、圖的空間嵌入及作為拓撲空間的圖，[1]還研究圖的浸入。
將圖嵌入曲面意味着在曲面（如球面）上繪製圖，而不使兩條邊相交。常作為數學謎題的基本嵌入問題是三間小屋問題，其他應用如印刷電子電路，即在電路板（面）上印刷（嵌入）電路（圖），且不短路。
作為拓撲空間的圖
對無向圖，可將抽象單純復形C與每個頂點的單元素集同每個邊的2元素集聯繫起來。復形的幾何實現|C|由每條邊的單位區間[0,1]的副本組成，這些區間的端點在頂點處粘合在一起。這樣來看，將圖嵌入曲面或作為其他圖的細分都是拓撲嵌入的實例，圖同胚只是拓撲同胚的特例，連通圖的概念與拓撲連通重合，並且當且僅當連通圖的基本群平凡時，才是樹。
與圖相關的其他單純復形還有團復形 （以圖的每個團為集合）與匹配復形（以圖的每個匹配為集合）（等同於線圖補集的團復形） 。完全二分圖的匹配復形稱作棋盤復形，因為其也可描述為棋盤上非攻擊車集合的復形。[2]
實例研究
約翰·霍普克洛夫特和羅伯特·塔揚[3]提出了一種圖的平面性檢驗的方法，且用時與邊數成線性關係。他們的算法通過構建圖嵌入（他們稱作「棕櫚樹」）實現。高效的平面性檢驗是圖形繪製的基礎。
金芳蓉等人[4]研究了書嵌入問題，圖的頂點沿書脊排列，圖的邊分別繪製在不同頁上，使同一頁的邊不交叉。這個問題抽象了多層印刷電路板布線問題。
另見
參考
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
