在图 $G$ 中，几何树宽是指存在一个划分 $\mathcal{P}$，使得 $G/\mathcal{P}$ 的树宽为最小 $k$。基于该概念，行树宽被定义为存在一个图 $H$（树宽为 $k$）和路径 $P$，使得 $G \subseteq H \boxtimes P$ 的最小 $k$。行树宽的另一种等价定义是，存在一个划分 $\mathcal{P}$，使得划分中的地理线段在某种分层下对齐，且 $G/\mathcal{P}$ 的树宽为 $k$。
我们通过展示行树宽的有界性并不意味着几何树宽的有界性来区分这两者。此外，我们提出了一种多项式时间算法，用于判断树宽为 2 的图是否具有几何树宽为 1，已知行树宽的这一问题是 NP-hard 的 [Biedl, Eppstein, Ueckerdt, 2025]。
更一般地，我们提供了一种算法，决定给定图的几何树宽是否最多为 $d$，该算法在树宽上是 XP，而行树宽则没有这样的算法，除非 P = NP [Biedl, Eppstein, Ueckerdt, 2025]。
另一方面，我们证明了计算几何树宽是 NP-hard 的，并且每个几何树宽为 1 的图具有有界的行树宽。此外，我们将平面图的几何树宽的已知下界提高到 5。
博主点评： 本文通过清晰的定义和算法展示了几何树宽与行树宽之间的本质差异，尤其是在复杂性理论中的重要性。算法的多项式时间性质为图的树宽研究提供了新的思路，值得关注。