图的厚度

厚度（或深度） (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)。