在
图论中,图G的厚度是可以对G的边缘进行分割的
平面图的最小数量。 也就是说,如果存在k个平面图的集合,它们具有相同的顶点集,且这些平面图的并集是G,那么G的厚度最多为k。换句话说,图G的厚度是图G的平面子图的最小数目(而图G是这几个子图的并集)。
在图论中,图G的厚度是可以对G的边缘进行分割的平面图的最小数量。 也就是说,如果存在k个平面图的集合,它们具有相同的顶点集,且这些平面图的并集是G,那么G的厚度最多为k。换句话说,图G的厚度是图G的平面子图的最小数目(而图G是这几个子图的并集)。
因此,平面图具有厚度1。厚度2的图形称为双平面图(biplanar graphs)。 厚度的概念源于1962年Frank Harary的猜想:对于9点的任何图形,它的本身或其互补图形都是非平面的。 这个问题等同于确定完整图K9是否是双平面的。佩特拉·穆泽尔、托马斯·奥登塔尔和马克·沙尔布罗特撰写了关于1998年主题艺术状况的综合性调查。
每个
森林(在图论中,森林由不相交的树组成)都是平面的,每个平面图都可以最多划分成三个森林。 因此,任何曲线G的厚度最多等于相同图形的
轮廓(轮廓是其边缘可以分割成的森林的最小数量),至少等于轮廓除以3。G的厚度也在另一个标准图不变量的恒定因子内,定义为子图中G的最大值。 如果n顶点图具有厚度t,那么它必然具有至多t(3n-6)轮廓,从而遵循其简并度至多为6t -1。在另一方向,如果图具有简并D,则厚度最多为D。
厚度与同时嵌入的问题密切相关,如果两个或更多个平面图都共享相同的顶点集,则可以将所有这些图形嵌入平面中,其中按照轮廓绘制为曲线,使得每个顶点在所有不同的图形中具有相同的位置。 然而,将边缘绘制成直线段可能不会构造这样的图形。
曲线G的直线厚度或几何厚度计算可分解成的平面图的最小数量,受限于所有这些图形可以与直边同时绘制的数量。所有顶点都绘制成凸起的位置,形成图形的圆形布局,又增加了额外的限制。 然而,这三个厚度参数中的两个总是处于彼此恒定的因子之内。