平面性輔助圖(planarity auxiliary graph)是一類特殊的圖，它是由判定一個圖的平面性而引出的另一個圖，根據這個圖是否有某種性質的圈來判定原來的圖是否是可平面的，首先，用確向術(深探、左探或右探)求圖G上的一個支撐樹T，並給出G的一個對於T的樹浸入，將T的邊依端點出現的次序給以定向，以每一個節點(除樹梢外)處的這樣的邊對作為新節點，在邊對中必有一邊為樹邊且方向為離開這個節點而另一邊不為那條指向這個節點的樹邊，對於任何一對不相鄰的上樹邊，若它們的基本圈至少有一個公共節點，則必有兩個相應新節點的邊對，其中兩邊分別落在兩個基本圈上，從而，可以引進一條新邊連此兩新節點，並且，在新邊上可以賦以一個權，即，當此新邊相應的邊對在這個樹嵌入中相交奇數個點時為1；否則，為0，這樣的一個由新節點和新邊所得帶權的新圖，就稱為平面性輔助圖，記為Aux(G)。
基本介紹
- 中文名：平面性輔助圖
- 外文名：planarity auxiliary graph
- 首引：劉彥佩
基本介紹,相關定理,
基本介紹
平面性輔助圖是劉彥佩於1978年首先引進的，由Aux(G)是否有奇權的圈就可以判定G是否為可平面的，一般而言，Aux(G)的階和度均不超過原圖階的一個二次函式，以後又引進了第一類和第二類的平面性輔助圖以得到線性時間的算法，Aux(G)也稱為第0類輔助圖，在第一類平面性輔助圖中節點只是第0類節點集的一個子集，它相應於那些含有一條樹邊和一條上樹邊的邊對，這就保證了它的階不超過原圖階的一個線性函式，然而邊的集合則必須要重新構造，而第二類平面性輔助圖的節點集與第一類的相同，但邊的集合是第一類的一個子集，並且使得它的度也不超過原圖階的一個線性函式，這就從理論上導致判定圖的平面性與求平面嵌入都可以用線性時間算法實現.平面性輔助圖不僅在判定圖的平面性以及進行平面嵌入時有用，而且，在確定圖的不可分離連通塊以及3連通塊、列出所有不等價的平面嵌入、圖的平面分解以及判定平面圖的同構、圖的曲面嵌入等方面均有套用。
相關定理
定理1 一個連通圖G是可平面的，若且唯若對於一個T-浸入μ，方程組
引理1 在(1)中每一個方程均有形式：對給定的，
定理2 一個圖G(當然，連通的)是可平面的，若且唯若對於G的一個T-浸入方程組
定理3 對於G的一個T-浸入μ，方程(3)有解，若且唯若對於G的一個確向浸入
方程
引理3 對於一個確向浸入，方程(4)有解當僅當在
上無奇權圈。
定理4 對於圖G的一個確向浸入，方程(4)有解若且唯若對上的一個樹(通常為森，但總可設為樹而不失一般性)
，在中無奇權的基本圈。
