圖的厚度

厚度（或深度） (Skiena 1990, p. 251; Beineke 1997) 或 (Harary 1994, p. 120) 一個 圖 是 平面 邊匯出子圖 的最小數量，使得 圖的並 (Skiena 1990, p. 251)。

平面圖 的厚度因此為 ，而 非平面圖 的厚度滿足 。 由兩個平面圖的並組成的圖（即，厚度為 1 或 2）被稱為 雙平面圖 (Beineke 1997)。

確定圖的厚度是一個 NP 完全問題 (Mansfeld 1983, Beineke 1997)。 許多小型命名或索引圖的預計算厚度可以在 Wolfram 語言 中使用以下命令獲得GraphData[圖,"厚度"].

圖的厚度的下界由下式給出

(1)

其中 是邊的數量， 是頂點的數量， 是 向上取整函式 (Skiena 1990, p. 251)。 上面的例子展示了 完全圖 分解為三個平面子圖。 這個分解是最小的，因此 ，與界限 一致。

根據 Brooks 定理，圖的厚度最多比圖的 區域性交叉數 大 1 (Kainen 1973, Thomassen 1988)。

完全圖 的厚度滿足

(2)

除了 (Vasak 1976, Alekseev and Gonchakov 1976, Beineke 1997)。 對於 , 2, ..., 厚度因此為 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, ... (OEIS A124156)。

完全二分圖 的厚度由下式給出

(3)

除非可能在 和 都是奇數的情況下，並且，取 ，存在一個偶數整數 且 (Beineke et al. 1964; Harary 1994, p. 121; Beineke 1997, 其中 Beineke 1997 給出的例外條件中的向上取整已更正為向下取整)。 最小的此類例外值總結在下表中。

13	17	4
17	21	5
19	29	6
19	47	7
21	25	6
23	75	9
25	29	7
25	59	9

根據 Beineke (1997)， 的例外二分指數的唯一子集是 、、、 和 。

的厚度因此由下式給出

(4)

(Harary 1994, p. 121)，對於 , 2, ... 給出值 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, ... (OEIS A128929)。

最後，超立方體圖 的厚度由下式給出

(5)

(Harary 1994, p. 121)，對於 , 2, ... 給出值 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 6, (OEIS A144075)。

還引入了圖厚度的許多變體，例如外平面厚度、樹蔭數、書厚度和環面厚度 (Beineke 1997)。