平面嵌入

平面嵌入是圖在平面上的一種表示。若圖G同構於平面圖P，則稱P是圖G的一個平面嵌入。若P的每條邊都是一條直線段，則稱P是圖G的直線嵌入；若P的每個有限面都是一個凸區域，則稱P是圖G的凸嵌入；若P的每條邊都是由相繼的水平線段和鉛垂線段組成的折線，則稱P是圖G的縱橫嵌入。

基本介紹

• 中文名：平面嵌入
• 外文名：planar embedding
• 適用範圍：數理科學

定義

若圖G同構於平面圖P，則稱P是圖G的一個平面嵌入。

若P的每條邊都是一條直線段，則稱P是圖G的直線嵌入；

若P的每個有限面都是一個凸區域，則稱P是圖G的凸嵌入；

若P的每條邊都是由相繼的水平線段和鉛垂線段組成的折線，則稱P是圖G的縱橫嵌入。

一條邊上水平線段與鉛垂線段的交點稱為一個折。

若P的每條邊都是水平或鉛垂的直線段，則稱P是圖G的格線嵌入。

在圖G的所有縱橫嵌入中，折的總數最小的嵌入稱為圖G的最小折數嵌入。

在圖G的所有縱橫嵌入中，所有有限面的面積和最小的嵌入稱為最小面積嵌入。

縱橫嵌入的理論是在超大規模積體電路(VLSI)設計中引出的。關於最小折數以及最小面積的確定，一般是很困難的或者說，屬於NP完全的問題。

平面圖

〔plane graph〕

設圖 G 是畫在平面上的圖，若 G 的任兩條邊除端點外都是不相交的，則稱 G 為平面圖。

與平面圖同構的圖稱為可平面圖（planar graph）。一個可平面圖畫到平面上使其為平面圖，則稱之為平面嵌入（planar embedding）。

不是平面圖的圖稱為非平面圖（nonplanar graph）。平面圖將平面劃分為邊相連的開集，這些開集稱為平面圖的面（face）。

如果一個可平面圖存在一個所有頂點都在外面的邊界上的平面嵌入，則它稱為外平面圖（outerplanar graph）。

判斷給定圖是否可平面以及如何把一個可平面圖嵌入平面是平面圖理論研究的主要問題之一。

根據平面圖的定義可知，可平面圖的任意子圖是可平面圖；圖 G 是可平面圖的若且唯若 G 的每一部分圖是可平面的。設圖G是具有n個頂點，m條邊和f個面連通平面圖，歐拉在1752年，給出了平面圖G的一個必要條件:，這就是歐拉公式（Euler‘s formula）。

由歐拉公式可以證明：若圖G為有至少三個頂點的簡單可平面圖,則圖 G 的邊數，等號成立若且唯若 G 的每一個平面嵌入都是三角剖分的。容易證明和都是非平面圖。

1930年，庫拉托夫斯基（C.Kuatowski）證明一個圖 G 是可平面圖若且唯若它不含和的部分。

給定平面圖 G ,可以定義另一個圖 G* 如下:對於G的每個面 f ，都有 G* 的頂點 f 與之對應；對於 G 的每條邊 e,都有 G* 的邊 e* 與之對應，G* 中的頂點 f* 與 g* 由邊 e* 連線當前僅當 G 中與頂點 f* 和 g* 對應的面 f 和 g 被邊 e 分隔。圖 G* 稱為 G 的對偶圖（dual graph）。可以證明，任意平面圖的對偶圖都是連通的。若平面圖 G 和它的對偶圖同構，則稱 G 為自對偶圖（self-dual graph）。