在圖論中，平面圖是可以画在平面上并且使得不同的邊可以互不交疊的圖。而如果一个图无论怎样都无法画在平面上，并使得不同的边互不交叠，那么这样的图不是平面图，或者称为非平面图。完全图 K5和完全二分图 K3,3（湯瑪森圖）是最“小”的非平面图。
一個將平面圖畫在平面上的方法稱為平版圖，又稱為圖的平面嵌入，更精確地說，平版圖包含一個平面圖與一個映射，此映射將平面圖的頂點對應到平面上的一點，邊對應到一條平面曲线段，滿足邊兩端點對應到線段的兩端點，並且線段之間除了在端點之外都不相交。
藉由球极投影可知一個圖可以被嵌入平面若且唯若可以被嵌入球面。圖的球面嵌入在關係中的等價類稱為平面映射。注意到一個平版圖會有外圍面，又稱無界面，但因為平面映射定義是在球面上的等價類，不會有任何一個面有這個特殊的地位。
平面圖可以被視為一個。
平面圖的條件
库拉托夫斯基定理
1930年，波蘭數學家卡齐米日·库拉托夫斯基提出的一類禁用準則（指滿足某種條件的圖就一定無法具有某個性質）中，包括了平面圖的情況。這個定理現在被稱作库拉托夫斯基定理：一個简单图是平面圖若且唯若它並不包含一個是 K5 或 K3,3 的分割的子圖。
其中， K5 代表有 5 個點的完全圖，K3,3 代表兩部分各 3 個點的完全二分圖，分割的定義如下。考慮一個作用，將一個邊中間插入一個頂點，如下圖
可以將圖 B 做有限次的上述操作可以得到圖 A，則稱 A 是 B 的細分圖。
用圖的同胚理論來說，就是一個有限圖是平面圖若且唯若這個圖不包含任何同胚於K_5或K_{3,3}的子圖。
這個定理的一般化是羅伯森－西摩定理。
華格納定理
在隨後的1937年，德國數學家提出了類似的禁用定理，華格納定理：一個简单图是平面圖若且唯若它不是 K5 或 K3,3 的次圖。
其中，一個圖的次圖是將它做有限多次的取子圖(刪除部分頂點和邊)和做邊收縮(將某邊縮成一個頂點)所得到的圖。
平面圖和球面嵌入
說一個圖是平面圖，其實等價於說存在一個從空間到平面的連續的單射，能夠將這個圖投射到平面上。從這樣的角度看來，平面圖是空間的一部份在二維平面上的一個嵌入。然而，圖在二維平面的嵌入和在球面的嵌入是等價的：
證明是顯而易見的：首先，如果一個圖是平面圖，那麼將它畫在一張紙上，並在“墨跡未乾”之時將這張紙“拓印”在一個足夠大的球面上（這樣紙基本不會皺）。於是，就得到了一個畫在球面上的同樣的圖。反過來，如果能把一個圖畫在球面上而沒有交互重疊的邊，那麼，把球放在一個無限大平面上，并將球稍作滾動，使得球的最高點不在圖的邊或頂點上。然後，以最高點為中心，把球面（出了最高點）投影在平面上，那麼，得到的平面圖形和原來的圖是一樣的，而且沒有交互重疊的邊，所以原來的圖也是平面圖。
依此準則，空間中的各種凸多面體對應的圖都是平面圖，因為只要在多面體的內部找一個合適的球，然後將多面體的頂點和邊都投影在這個球面上，就完成了相應的圖在球面的嵌入（由於多面體是凸的，投影得到的圖形的邊之間不會交疊）。比如說，所有的正多面體對應的圖都是平面圖。
圖的 1-外圍平面嵌入是一般的外圍平面嵌入。對所有 k>1，一個圖的平面嵌入是 k-外圍平面嵌入若且唯若將他刪掉外圍面邊界上的所有頂點會形成一個 (k-1)-外圍平面嵌入。一個圖如果有一個 k-外圍平面嵌入則被稱為是一個 k-外圍平面圖。
不環繞嵌入圖
所有圖都可以被嵌入三維空間中使得各邊不交叉，特別的，如果該圖存在一個嵌入額外滿足圖中的兩個互斥環對應到三維空間中的兩個互不環繞的封閉曲線(環繞數為0)，則該圖被稱為是一個。不環繞嵌入圖可以被看做是平面圖的三維空間版本，所以也有類似華格納定理的禁用結果：一個簡單圖是平面圖若且唯若它不是中所有的 7 個圖之一的次圖。類似的，平面圖和外圍平面圖分別對應到小於等於 2 和 3 的圖，而環繞嵌入圖對應到科蘭·德·韋迪耶爾不變量小於等於 4 的圖。
哈林圖
哈林圖是一個平面圖，是將一個不包含度數為 2 的頂點的樹的葉子由一個環連結起來所得到的圖。等價的，哈林圖是一個多面體圖滿足有一個面與其他所有的面都相鄰。如同外圍平面圖，哈林圖的也很低，因此哈林圖相關的演算法問題會比一般的平面圖來的好處理許多。
其他相關的圖
一個圖是如果它可以刪去某一個頂點之後變成平面圖，一個圖是 k-尖點圖如果如果它可以刪去某 k 個頂點之後變成平面圖。
一個圖是如果它可以畫在平面上使得每條邊至多和所有其他邊交叉一次，一個圖是 k-平面圖如果它可以畫在平面上使得每條邊至多和所有其他邊交叉 k 次。
給定一個地圖，滿足上面的各個區域都是單連通且兩兩只在邊界上有交集。將各個區域視為頂點，兩區域的邊界若有交集則連邊，所獲得的圖稱為。如果在原地圖上，至多三個區域有共同交集，則定義出來的地圖圖是平面圖，但若存在四個以上的區域相交在同一個點上，在定義出來的地圖圖可能是非平面圖。
一個圖被稱為如果它可以被嵌入环面使得各邊不交叉。更廣義的來說，一個圖的虧格被定義為所有該圖可以嵌入而邊不交叉的曲面中虧格的最小值。因此，平面圖的虧格為 0 而非平面的環面圖的虧格為 1。
一個是可以被畫在平面上的有向無環圖，使得各個有向邊都是斜向上的。並不是所有平面有向無環圖都是向上平面圖，事實上，決定任意給定有向圖是否為向上平面圖的難度是 NP完全的。
平面圖的數量估計
若將頂點標號，有 n 個頂點的平面圖的數量的漸近式由g\cdot n^{-7/2}\cdot \gamma^n\cdot n!給出，其中常數{\displaystyle \gamma \approx 27.22687}、{\displaystyle g\approx 0.43\times 10^{-5}}；若不將頂點標號，有 n 個頂點的平面圖的數量則界在 2.72^n和 30.06^n之間。
幾乎所有的平面圖的自同構數量隨著頂點數的增加呈現指數增長。
其他性質與定義
四色定理敘述說任何平面圖都可以被 4-著色。
說所有簡單平面圖都從在一種平面嵌入法使得各邊對應到互相不相交的線段，在平面上一個有 n 點地集合被稱為如果所有 n 點的平面圖都可將頂點對應到它們，而且邊是互不相的直線。例如 4 個頂點的泛頂點集是所有滿足其中一個點在另外三個點圍成的三角形的內部。任何外圍平面圖可以被畫在平面上滿足所有頂點在給定的圓上面，所有邊是互不相的直線且都落在圓裡面。
一個平面圖被稱作是凸 的如果他可以被畫在平面上，使得各個面，包括外圍面，都是凸多邊形。一個圖是凸平面圖若且唯若它是一個平面圖的分割。
(現在是定理) 說所有平面圖都可以表示成平面上一些線段的。
說給定任何包含 n 個頂點的平面圖，都可以藉由移除至多 O(\sqrt n)個點來將原圖分開成兩個部分，並且各部份的頂點數不超過 \frac 2 3 n個。由此可推得平面圖的和至多 O(\sqrt n)。
存在複雜度為 O(n) 演算法來判斷兩個 n 點的平面圖是否同構，參見圖同構問題。
欧式图是一个以平面上的点以及之间用欧几里得距离的边连接的图。
定义为一个平面图的面个数除以 2n-5 (平面图最大的面数）。所以网格化系数最小是0（树），最大是1。
平面图包含了一个没有三角形的平面图，更一般的说，是可3着色的平面图。
對偶圖
設 G 是一個平版圖，G 不見得是簡單圖，定義 G 的對偶圖 G 如下述。在 G 中的每個面 (包括外圍面) 取一個點，作為 G 的頂點，對於 G 中的每個邊 e，畫一條 G 中的邊 e 連接與 e 相鄰的兩個面中的頂點，而且 e 要穿過 e。如果與 e 相鄰的兩面是同一個，則對該面中的點畫一個穿過 e 的自環，如果 G 中兩相鄰面的交界包含多個邊，則 G 中的兩點之間要連多條邊，如右圖。
此時對偶圖 G 也是平版圖，而且如果 G 是連通的，則 G 與 G 在球面上是拓樸等價的，換句話說，他們是相同的平面映射。如果 G 是多面體 Γ 對應到的多面體圖，則 G 是 Γ 對應到的多面體圖，其中 Γ 是 Γ 的對偶多面體。
對偶圖的重要性在於，對偶圖和原圖的性質的關係往往是易於刻劃的，因此，有時研究一個平版圖 (或平面圖) 的對偶圖的性質有助於對原圖的了解。注意到，一個平版圖的對偶圖在拓樸等價下是唯一的，但一個平面圖可能有多種平面嵌入的方式，因此可能會對應到多個不同的對偶圖。
參考來源
外部連結
- [http://www.planarity.net/ Planarity] ：通過改變頂點的位置，令圖的邊互不重疊的遊戲
评论 (0)