厚度（圖理論）

在圖理論中，圖G的厚度是可以將G邊緣分區的最小平面圖數量。也就是說，如果存在K平面圖的集合，則所有這些都具有相同的頂點，使得這些平面圖的結合為G ，那麼G的厚度最多為k 。換句話說，圖的厚度是平面子圖的最小數量，其聯合等於圖g 。

因此，平面圖具有厚度1.厚度2的圖稱為雙波達圖。厚度的概念起源於地球 - 幾個月問題，在Biplanar圖的色數上，由Gerhard Ringel於1959年提出，以及1962年的1962年Frank Harary的猜想：對於9分的任何圖表，本身或其互補圖是非平面。問題等同於確定完整的圖k ₉是否為biplanar（不是，猜想是正確的）。截至1998年起，一項關於該主題的藝術狀況的全面調查是由佩特拉·穆茨（Petra Mutzel） ，托馬斯·奧德達爾（Thomas Odenthal）和馬克·沙布羅德（Mark Scharbrodt）撰寫的。

特定圖

n頂點k _n上完整圖的厚度為

除非n = 9，10厚度為三個。

除某些例外，完整的二分圖k _a，b的厚度通常為：

特性

每個森林都是平面，每個平面圖最多都可以分為三個森林。因此，任何圖G的厚度最多等於同一圖的樹木（可以被分區的最小森林數量），並且至少等於支子長除以三個。

最大程度的圖最多有厚度 。這不能改進：對於 - 至少帶有周長的圖表 ，高圍欄迫使任何平面子圖都稀疏，導致其厚度恰好是 。

厚度的圖和頂點最多有邊緣。因為這給他們平均程度少於 ，他們的墮落最多是他們的色數最多是 。在這裡，脫落率可以定義為亞給達圖的最大值，而不是給定圖的子圖。在另一個方向上，如果圖具有退化性那麼它的支撐性和厚度最多是 。一個人可以找到每個頂點最多具有的圖形頂點的順序比訂購時要晚的鄰居，並將這些邊緣分配給不同的子圖將圖表的分區產生到樹是平面圖。

即使在這種情況下 ，色數的確切值未知；這是Gerhard Ringel的地球 - 幾個問題。湯姆·蘇蘭克（Thom Sulanke）的一個例子表明， ，至少需要9種顏色。

相關問題

厚度與同時嵌入的問題密切相關。如果兩個或多個平面圖都共享相同的頂點集，則可以將所有這些圖嵌入平面中，邊緣將邊緣繪製為曲線，以便每個頂點在所有不同的圖紙中都具有相同的位置。但是，在保持邊緣作為直線段時，可能無法構造這樣的圖紙。

圖G圖G的直率厚度或幾何厚度的不同圖形不變性，計算了最小數量的平面圖，可以將G分解為g，受到限制，即所有這些圖形都可以同時繪製使用直邊的同時繪製。本書的厚度增加了一個額外的限制，即所有的頂點均以凸位，形成圖形的圓形佈局。然而，與建立和墮落的情況相反，這三個厚度參數中沒有兩個始終在彼此的恆定因素之內。

計算複雜性

計算給定圖的厚度是NP- hard ，而NP完整的測試厚度最多是兩個。然而，與樹木的連接允許在多項式時間內近似於3的近似值之比。