图的厚度问题

图的厚度是图论中研究图在平面上的结构复杂性的一个重要参数。它衡量的是将一个图分解为若干个平面子图所需的最小数目。下面我们逐步展开这个概念。

1. 背景与定义

   • 平面图是指可以画在平面上使得边仅在顶点处相交的图。但许多图（如完全图K₅或完全二分图K₃,₃）是非平面图。
   • 厚度（thickness）定义为：将一个图G的边集划分为k个不相交的子集，使得每个子集导出的子图都是平面图，满足此条件的最小k值称为G的厚度，记作θ(G)。
   • 直观理解：厚度表示需要用多少个"平面层"才能无交叉地绘制G。例如，θ(G)=1当且仅当G是平面图。

2. 厚度与图参数的关系

   • 厚度与顶点数n和边数m相关：对简单图，有下界θ(G) ≥ ⌈m/(3n-6)⌉（利用平面图最多有3n-6条边）。
   • 与图的最大团或密度相关：完全图Kₙ的厚度有公式θ(Kₙ) = ⌊(n+7)/6⌋（n≠4,9时成立，特殊情况需调整）。
   • 厚度与图的连通性无直接必然联系，但高密度图通常厚度更大。

3. 计算复杂性与已知结果

   • 判断θ(G)≤k是NP-难问题（k≥2时），即使对二分图也困难。
   • 特定图类的厚度已知：
     • 树和森林：厚度为1（平面图）。
     • 完全二分图Kₐ,ᵦ：厚度为⌈ab/(2a+2b-4)⌉。
     • 超立方体图Qₙ：厚度为⌈(n+1)/4⌉。

4. 厚度与其它"分层"参数对比

   • 与色数不同：厚度关注边分解为平面子图，而色数是顶点着色问题。
   • 与算术厚度（需同时满足顶点和边的平面嵌入）相比，厚度只约束边集。
   • 与书厚度（book thickness）相关：书厚度要求边沿书脊排列，而厚度允许更自由的平面嵌入。

5. 应用与扩展

   • 电路设计：厚度对应多层电路板的最小层数，以减少交叉。
   • 拓扑图论：厚度与图的亏格（genus）有关，满足θ(G) ≤ γ(G)+1（γ是亏格）。
   • 开放问题：确定一般图厚度的紧上界仍为难题，尤其是对于稀疏但非平面的图结构。

厚度问题本质是图平面性的一种"分层推广"，它连接了图的可嵌入性与实际工程约束，是拓扑图论中兼具理论与应用价值的经典课题。