树宽

图论中，无向图的树宽（treewidth）是描述图与树的距离的正整数。树宽为1的图就是树或森林。树宽不大于2的图叫做系列并行图。树宽恰为k的最大图称作k树，树宽不大于k的图称作部分k树。很多有充分研究的图族的树宽也是有界的。

树宽可用几种等价方式正式定义：图的树分解中最大顶点集的大小、图的弦补全中最大团的大小、描述图上追逃对策的港的最大阶数、刺藤（bramble，相互接触的连通子图的集合）的最大阶数。

树宽常用作图算法的参数复杂性分析中的参数。对一般图NP困难的许多算法，将树宽固定于常数时就变得容易了。

树宽的概念最初由Umberto Bertelè and Francesco Brioschi （1972）提出，叫做“维度”（dimension）。后来，Rudolf Halin （1976）根据树宽和哈德维格数的共同属性，重新发现了树宽。Neil Robertson and Paul Seymour （1984）又重新发现了树宽，自此才获得了学界的关注。^{[1]:354–355}

定义

 

将8顶点图分解为6结点树的树分解。边两端的两顶点在树的某个结点排列在一起，每个图顶点则在连续子树的结点上排列。树结点最多列出3个顶点，因此该分解的宽为2。

图${\displaystyle G=(V,\ E)}$ 的树分解是结点为${\displaystyle X_{1},\ \dots ,\ X_{n}}$ 的树T，其中${\displaystyle X_{i}}$ 都是V的子集，满足下列性质^[2]（为避免与G的顶点混淆，“结点”仅指树T的顶点）：

1. ${\displaystyle \bigcup _{i}X_{i}=V.}$ 即，图顶点至少包含在一个树结点中。
2. 若${\displaystyle X_{i},\ X_{j}}$ 共同包含顶点v，则在${\displaystyle X_{i}}$ 到${\displaystyle X_{j}}$ 的（唯一）路径上，T的所有结点${\displaystyle X_{k}}$ 也都包含v。即，包含顶点v的树结点构成T的连通子树。
3. 对图中每条边${\displaystyle (v,\ w)}$ ，存在同时包含v、w的子集${\displaystyle X_{i}}$ 。即，只有当相应的子树有共同结点时，图顶点才是相邻的。

树分解的宽是其最大集${\displaystyle X_{i}}$ 的大小减一。图G的树宽${\displaystyle {\rm {tw}}(G)}$ 等于G的树分解的最小宽度，按这定义，最大集的大小减一，树的树宽才能等于一。

等价地，G的树宽等于团数最小的含G弦图中最大团的大小减一。在G中属于${\displaystyle X_{i}}$ 的两顶点间添加一条边，就可得到团大小相符的弦图。

树宽也可用港描述，其是在图上定义的追逃对策中逃逸策略的函数。若有至多${\displaystyle k+1}$ 阶的港——函数${\displaystyle \beta }$ ，将G中最多k个顶点的集合X映射到${\displaystyle G\backslash X}$ 的一个连通分量中，并且具有${\displaystyle X\subseteq Y\Rightarrow \beta (Y)\subseteq \beta (X)}$ 的单调性，就称图G的树宽为k。

 

3×3格图中的4阶刺藤，其存在表明图的树宽至少为3

使用刺藤（bramble）也可做出类似描述。刺藤是指一族相互接触的连通子图（即共享一个顶点，或由一条边连接）。^[3]刺藤的阶数是子图族的最小命中集（hitting set），图的树宽等于刺藤最大阶数减一。

例子

完全图${\displaystyle K_{n}}$ 的树宽为${\displaystyle n-1}$ 。这用树宽的弦图定义很容易看出来：完全图已经是弦图，添加更多边不能减小最大团的大小。

当且仅当至少2顶点的连通图是树，连通图的树宽为1。树的树宽为1，与完全图同理（即它已经是弦图，且最大团大小为2）。反之，若图中有循环，则所有弦补全都至少包括一个由循环的3个连续顶点组成的三角形，由此可见其树宽至少为2。

有界树宽

有界树宽图族

树宽不大于常数k的图称作部分k树。其他具有有界树宽的图族，有仙人掌图、伪森林、系列并行图、外平面图、哈林图、阿波罗尼奥斯网络等。^[4]在结构化编程的编译阶段出现的控制流图，树宽也是有界的，使寄存器配置之类任务可在其上高效执行。^[5]

平面图的树宽不一定有界，因为${\displaystyle n\times n}$ 格图是树宽恰为n的平面图。于是，若F是树宽有界的子式闭图族，则它不可能包含所有平面图。反之，若某平面图不能作为F族中图的子式出现，则存在常数k，使F中所有图的树宽不大于k。即，以下3个条件等价：^[6]

1. F是树宽有界图的子式闭图族；
2. 表征了F的有限多禁子式（forbidden minor）中，有一个是平面的；
3. F是不含平面图的子式闭图族。

禁子式

 

树宽为3的4个禁子式：${\displaystyle K_{5}}$ （左上）、八面体图（左下）、瓦格纳图（右上）、五棱柱图（右下）

对每个有限值k，树宽不大于k的图都可用禁子式的有限集表示（即，任意树宽大于k的图，都包含集合中的一个图作为子式）。每个这样的禁子式集都包含平面图。

• 对于${\displaystyle k=1}$ ，唯一的禁子式是3-顶点循环图。^[7]
• 对于${\displaystyle k=2}$ ，唯一的禁子式是4-顶点完全图${\displaystyle K_{4}}$ 。^[7]
• 对于${\displaystyle k=3}$ ，有4个禁子式：${\displaystyle K_{5}}$ 、八面体图、五棱柱图、瓦格纳图。其中两个多面体图是平面图。^[8]

对更大的k，禁子式的增长速度不小于k的平方根指数。^[9]但已知的禁子式的大小与数量的上界远高于这个下界。^[10]

算法

计算树宽

判断给定图G的树宽是否不大于给定值k的问题，是NP完全的。^[11]而当k为任意固定常数时，可在线性时间内识别出树宽为k的图，并为之构造出树宽为k的树分解。^[12]这算法的耗时对k是指数级的。

由于树宽在众多领域中的作用，人们开发了计算树宽的各种算法。根据具体的应用，我们可以选择更好的近似率，或运行时间与输入或树宽大小更相关的算法。 下表概述了一些树宽算法。其中，k是树宽，n是输入图G的顶点数。每种算法都能在${\displaystyle f(k)\cdot g(n)}$ 的时间内输出宽度等于“近似”栏中的分解图。例如，Bodlaender (1996)的算法在${\displaystyle 2^{O(k^{3})}\cdot n}$ 时间内，要么为输入图G构建树宽不大于k的树分解，要么报告G的树宽大于k。相似地，Bodlaender 等人 (2016)的算法在${\displaystyle 2^{O(k)}\cdot n}$ 时间内，要么为输入图G构建树宽不大于${\displaystyle 5k+4}$ 的树分解，要么报告G的树宽大于k。Korhonen (2021)在同样运行时间内，将其改进到${\displaystyle 2k+1}$ 。

近似	${\displaystyle f(k)}$	${\displaystyle g(n)}$	参考文献
精确	${\displaystyle O(1)}$	${\displaystyle O(n^{k+2})}$	Arnborg，Corneil & Proskurowski (1987)
${\displaystyle 4k+3}$	${\displaystyle O(3^{3k})}$	${\displaystyle O(n^{2})}$	Robertson & Seymour (1995)
${\displaystyle 8k+7}$	${\displaystyle 2^{O(k\log k)}}$	${\displaystyle n\log ^{2}n}$	Lagergren (1996)
${\displaystyle 5k+4{\text{或}}7k+6}$	${\displaystyle 2^{O(k\log k)}}$	${\displaystyle n\log n}$	Reed (1992)
精确	${\displaystyle 2^{O(k^{3})}}$	${\displaystyle O(n)}$	Bodlaender (1996)
${\displaystyle O\left(k\cdot {\sqrt {\log k}}\right)}$	${\displaystyle O(1)}$	${\displaystyle n^{O(1)}}$	Feige，Hajiaghayi & Lee (2008)
${\displaystyle 4.5k+4}$	${\displaystyle 2^{3k}}$	${\displaystyle n^{2}}$	Amir (2010)
${\displaystyle {\frac {11}{3}}k+4}$	${\displaystyle 2^{3.6982k}}$	${\displaystyle n^{3}\log ^{4}n}$	Amir (2010)
精确	${\displaystyle O(1)}$	${\displaystyle O(1.7347^{n})}$	Fomin，Todinca & Villanger (2015)
${\displaystyle 3k+2}$	${\displaystyle 2^{O(k)}}$	${\displaystyle O(n\log n)}$	Bodlaender 等人 (2016)
${\displaystyle 5k+4}$	${\displaystyle 2^{O(k)}}$	${\displaystyle O(n)}$	Bodlaender 等人 (2016)
${\displaystyle k^{2}}$	${\displaystyle O(k^{7})}$	${\displaystyle O(n\log n)}$	Fomin 等人 (2018)
${\displaystyle 5k+4}$	${\displaystyle 2^{8.765k}}$	${\displaystyle O(n\log n)}$	Belbasi & Fürer (2021a)
${\displaystyle 2^{O(k)}}$	${\displaystyle 2^{O(k)}}$	${\displaystyle O(n)}$	Korhonen (2021)
${\displaystyle 5k+4}$	${\displaystyle 2^{6.755k}}$	${\displaystyle O(n\log n)}$	Belbasi & Fürer (2021b)
精确	${\displaystyle 2^{O(k^{2})}}$	${\displaystyle n^{4}}$	Korhonen & Lokshtanov (2022)
${\displaystyle (1+\varepsilon )k}$	${\displaystyle k^{O(k/\varepsilon )}}$	${\displaystyle n^{4}}$	Korhonen & Lokshtanov (2022)

未解決的数学問題：平面图的树宽能否在多项式时间内算得？

目前还不知道确定平面图树宽的问题是不是NP完全的，也不知道其树宽能否在多项式时间内计算出来。^[13]

实践中，Shoikhet & Geiger (1997)的算法可以确定顶点数最多为100、树宽最多为11的图的树宽，并以最优树宽找到这些图的弦补全。

对更大的图，可以用基于搜索的技术，如分支定界搜索（BnB）与最佳优先搜索，以计算树宽。它们是任意时间算法，提前停止时会输出树宽的上界。

第一个计算树宽的BnB算法叫做QuickBB算法^[14]，是Gogate与Dechter提出的。^[15]BnB算法的质量在很大程度上取决于所用下限的质量，Gogate与Dechter^[15]还提出了一种计算树宽下界的新算法，称作minor-min-width。^[15]图的树宽绝不大于最小度数或其图子式，minor-min-width算法利用这一事实，在高层次上得出了树宽的下界。minor-min-width算法通过收缩最小度顶点与邻顶点间的边，反复构造图子式，直到仅剩一个顶点。所构造子式中，最小度的最大值是图树宽的下界。

Dow、Korf^[16]使用最佳优先搜索改进了QuickBB算法，在某些图上快了一个数量级。

解小树宽图上的其他问题

20世纪70年代初，人们发现，只要图的“维度”有界，就可通过非序列动态规划，高效解决一大类定义在图上的组合优化问题^[17]。Bodlaender (1998)的研究表明，“维度”等同于树宽。后来，多名学者在80年代末独立观察到，^[18]很多对任意图来说NP完全的问题，对树宽有界的图来说，可用动态规划，利用树分解高效解决。 举例来说，k树宽图的着色问题可通过对树分解使用动态规划算法解决。将${\displaystyle X_{i}}$ （树分解的所有集合）的顶点划分为颜色类，算法会结合储存在结点的相似类信息确定着色是否有效、扩展到树分解中所有的子结点。由此产生的算法能在${\displaystyle O(k^{k+O(1)}n)}$ 时间内找到n顶点图的最优着色，这个时间约能束使问题固定参数可解。

古赛尔定理

主条目：古赛尔定理

对于一大类问题，如果提供具有有界常值树宽的树分解，就可用线性时间算法求解。具体来说，古赛尔定理^[19]指出，若图问题可用一元二阶逻辑表为图的逻辑，就可在树宽有界图上用线性时间求解。一元二阶逻辑是一种描述图属性的语言，有下列结构：

• 逻辑运算，如${\displaystyle \wedge ,\vee ,\neg ,\Rightarrow }$ 
• 成员检验，如${\displaystyle e\in E,\ v\in V}$ 
• 对顶点、边、顶点集和/或边集的量词，如${\displaystyle \forall v\in V,\ \exists e\in E,\ \exists I\subseteq V,\ \forall F\subseteq E}$ 
• 邻接检验（如u是e的端点），及一些允许优化的扩展。

例如，考虑3着色问题。对图${\displaystyle G=(V,\ E)}$ ，此问题是说，有没有可能为每个顶点${\displaystyle v\in V}$ 分配3种颜色中的一种，使得相邻顶点总被分配不同颜色。 这个问题用一元二阶逻辑表为：

${\displaystyle \exists W_{1}\subseteq V:\exists W_{2}\subseteq V:\exists W_{3}\subseteq V:\forall v\in V:(v\in W_{1}\vee v\in W_{2}\vee v\in W_{3})\wedge }$ 

${\displaystyle \forall v\in V:\forall w\in V:(v,w)\in E\Rightarrow (\neg (v\in W_{1}\wedge w\in W_{1})\wedge \neg (v\in W_{2}\wedge w\in W_{2})\wedge \neg (v\in W_{3}\wedge w\in W_{3}))}$ ,

其中${\displaystyle W_{1},\ W_{2},\ W_{3}}$ 分别代表3种颜色的顶点子集。于是，根据古赛尔定理，对具有有界常值树宽的树分解的给定图，3着色问题可在线性时间内求解。

相关参数

径宽

图的径宽也是经过树分解定义的，不过其底树是径图，也可通过区间图定义，类似于由弦图定义树宽。因此，图的径宽总不小于树宽，但只能比树宽大一个对数因子。^[4]另一个参数是带宽，其定义与紧合区间图类似，径宽是其下界。其他相关参数还有树深，当且仅当子式闭图族中包含路径时有界；以及退化度，这是衡量图稀疏程度的指标，最多等于树宽。

格子式大小

由于${\displaystyle n\times n}$ 格图的树宽为n，图G的树宽总大于等于G的最大方格子式的大小。在另一个方向上，Robertson与Seymour的格子式定理表明，存在无界函数f使得最大方格子式的大小至少为${\displaystyle f(r)}$ ，其中r是树宽。^[20]f的已知最佳区间：对某常数${\displaystyle d>0}$ ，下界为${\displaystyle \Omega (r^{d})}$ ，上界为^[21]

${\displaystyle O\left({\sqrt {r/\log r}}\right).}$ 

关于下界中的Ω记号，见大O符号。对有约束的图族，区间也更严。双维理论为这些图族上的很多图优化问题提供了高效算法。^[22]哈林格定理提供了无限图的树宽与格子式大小关系的类比。^[23]

直径与局部树宽

若图族F在取子图下封闭，其中图的树宽有以直径为函数的上界，则称它们具有有界局部树宽或直径树宽性。若假设该族在取图子式下也封闭，则当且仅当F的一个禁子式是顶点图（apex graph），F才有有界的局部树宽。^[24]这一结果的最初证明显示，无顶点子式图族的树宽作为直径的函数，最多呈2倍指数增长；^[25]后来降为单倍指数增长^[22]，最后抵达线性的界。^[26]有界局部树宽与双维理论密切相关，^[27]一阶逻辑中可定义的图属性都可用略微超线性的时间来决定一个无顶点子式图族。 ^[28]

对取子式不封闭的图族，也有可能具有有界的局部树宽。特别是对一族有界度图来说，这是一定成立的，因为有界直径子图的大小有界。另一个例子是1-平面图，即可在平面上绘制的、每条边有1交叉的图，以及更广义地说，可在亏格有界的曲面上绘制的、每条边有一定交叉点的图。与局部树宽有界的子式闭图族一样，这一特征为图的高效近似算法指明了方向。^[29]

哈德维格数与S函数

Halin (1976)定义了一类叫做“S-函数”的图参数，其中包括树宽。这些函数从图映射到整数，无边图映射到0，具有子式单调性（若对函数f、G的子式H，总有${\displaystyle f(H)\leq f(G)}$ ，则称f是“子式单调”的），在与所有现有顶点相邻的位置添加新顶点时，函数值加1，并从团分隔两侧的两子图中取较大值。所有此种函数的集合在逐元素最小、最大化运算下，形成了完全格，当中的顶元素是树宽，底元素是哈德维格数，即给定图中最大完全子式的大小。

注释

1. Diestel (2005)
2. Diestel (2005) section 12.3
3. Seymour & Thomas (1993).
4. Bodlaender (1998).
5. Thorup (1998).
6. Robertson & Seymour (1986).
7. Bodlaender (1988).
8. Arnborg，Proskurowski & Corneil (1990); Satyanarayana & Tung (1990).
9. Ramachandramurthi (1997).
10. Lagergren (1993).
11. Arnborg, Corneil & Proskurowski (1987).
12. Bodlaender (1996).
13. Kao (2008).
14. Vibhav Gogate. personal.utdallas.edu. [2022-11-27]. （原始内容于2022-11-27）. 
15. Gogate, Vibhav; Dechter, Rina. A Complete Anytime Algorithm for Treewidth. 2012-07-11. arXiv:1207.4109   [cs.DS]. 
16. Best-First Search for Treewidth. www.aaai.org. [2022-11-27]. （原始内容于2022-01-22）. 
17. Bertelè & Brioschi (1972).
18. Arnborg & Proskurowski (1989); Bern，Lawler & Wong (1987); Bodlaender (1988).
19. Courcelle (1990); Courcelle (1992)
20. Robertson, Seymour. Graph minors. V. Excluding a planar graph. [1] （页面存档备份，存于互联网档案馆）  
21. Chekuri & Chuzhoy (2016)
22. Demaine & Hajiaghayi (2008).
23. Diestel (2004).
24. Eppstein (2000).
25. Eppstein (2000); Demaine & Hajiaghayi (2004a).
26. Demaine & Hajiaghayi (2004b).
27. Demaine 等人 (2004); Demaine & Hajiaghayi (2008).
28. Frick & Grohe (2001).
29. Grigoriev & Bodlaender (2007).

参考文献

• Amir, Eyal, Approximation algorithms for treewidth, Algorithmica, 2010, 56 (4): 448–479, MR 2581059, S2CID 5874913, doi:10.1007/s00453-008-9180-4 .
• Arnborg, S.; Corneil, D.; Proskurowski, A., Complexity of finding embeddings in a ${\displaystyle k}$ -tree, SIAM Journal on Matrix Analysis and Applications, 1987, 8 (2): 277–284, doi:10.1137/0608024 .
• Arnborg, Stefan; Proskurowski, Andrzej; Corneil, Derek G., Forbidden minors characterization of partial 3-trees, Discrete Mathematics, 1990, 80 (1): 1–19, MR 1045920, doi:10.1016/0012-365X(90)90292-P   .
• Arnborg, S.; Proskurowski, A., Linear time algorithms for NP-hard problems restricted to partial ${\displaystyle k}$ -trees, Discrete Applied Mathematics, 1989, 23 (1): 11–24, doi:10.1016/0166-218X(89)90031-0   .
• Belbasi, Mahdi; Fürer, Martin, An improvement of Reed's treewidth approximation, Uehara, Ryuhei; Hong, Seok-Hee; Nandy, Subhas C. (编), WALCOM: Algorithms and Computation – 15th International Conference and Workshops, WALCOM 2021, Yangon, Myanmar, February 28 - March 2, 2021, Proceedings, Lecture Notes in Computer Science 12635, Springer: 166–181, 2021a, MR 4239527, S2CID 222177100, arXiv:2010.03105  , doi:10.1007/978-3-030-68211-8_14 .
• Belbasi, Mahdi; Fürer, Martin, Finding all leftmost separators of size ${\displaystyle \leq k}$ , Du, Ding-Zhu; Du, Donglei; Wu, Chenchen; Xu, Dachuan (编), Combinatorial Optimization and Applications - 15th International Conference, COCOA 2021, Tianjin, China, December 17-19, 2021, Proceedings, Lecture Notes in Computer Science 13135, Springer: 273–287, 2021b, S2CID 242758210, arXiv:2111.02614  , doi:10.1007/978-3-030-92681-6_23 
• Bern, M. W.; Lawler, E. L.; Wong, A. L., Linear-time computation of optimal subgraphs of decomposable graphs, Journal of Algorithms, 1987, 8 (2): 216–235, doi:10.1016/0196-6774(87)90039-3 .
• Bertelè, Umberto; Brioschi, Francesco, Nonserial Dynamic Programming, Academic Press: 37–38, 1972 [2024-01-30], ISBN 978-0-12-093450-8, （原始内容于2024-01-30） .
• Bodlaender, Hans L., Dynamic programming on graphs with bounded treewidth, Proc. 15th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science 317, Springer-Verlag: 105–118, 1988, CiteSeerX 10.1.1.18.8503  , ISBN 978-3-540-19488-0, doi:10.1007/3-540-19488-6_110 .
• Bodlaender, Hans L., A linear time algorithm for finding tree-decompositions of small treewidth, SIAM Journal on Computing, 1996, 25 (6): 1305–1317, CiteSeerX 10.1.1.19.7484  , doi:10.1137/S0097539793251219 .
• Bodlaender, Hans L., A partial k-arboretum of graphs with bounded treewidth, Theoretical Computer Science, 1998, 209 (1–2): 1–45, doi:10.1016/S0304-3975(97)00228-4   .
• Bodlaender, Hans L.; Drange, Pal G.; Dregi, Markus S.; Fomin, Fedor V.; Lokshtanov, Daniel; Pilipczuk, Michal, A ${\displaystyle c^{k}n}$  5-approximation algorithm for treewidth, SIAM Journal on Computing, 2016, 45 (2): 317–378, arXiv:1304.6321  , doi:10.1137/130947374 .
• Chekuri, Chandra; Chuzhoy, Julia, Polynomial bounds for the grid-minor theorem, Journal of the ACM, 2016, 63 (5): A40:1–65, MR 3593966, S2CID 209860422, arXiv:1305.6577  , doi:10.1145/2820609 .
• Courcelle, B., The monadic second-order logic of graphs I: Recognizable sets of finite graphs, Information and Computation, 1990, 85: 12–75, CiteSeerX 10.1.1.158.5595  , doi:10.1016/0890-5401(90)90043-h .
• Courcelle, B., The monadic second-order logic of graphs III: Treewidth, forbidden minors and complexity issues., Informatique Théorique, 1992, (26): 257–286 .
• Demaine, Erik D.; Fomin, Fedor V.; Hajiaghayi, MohammadTaghi; Thilikos, Dimitrios M., Bidimensional parameters and local treewidth, SIAM Journal on Discrete Mathematics, 2004, 18 (3): 501–511, CiteSeerX 10.1.1.107.6195  , MR 2134412, S2CID 7803025, doi:10.1137/S0895480103433410 .
• Demaine, Erik D.; Hajiaghayi, MohammadTaghi, Diameter and treewidth in minor-closed graph families, revisited, Algorithmica, 2004a, 40 (3): 211–215, MR 2080518, S2CID 390856, doi:10.1007/s00453-004-1106-1 .
• Demaine, Erik D.; Hajiaghayi, MohammadTaghi, Equivalence of local treewidth and linear local treewidth and its algorithmic applications, Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, New York: ACM: 840–849, 2004b, MR 2290974 .
• Demaine, Erik D.; Hajiaghayi, MohammadTaghi, Linearity of grid minors in treewidth with applications through bidimensionality (PDF), Combinatorica, 2008, 28 (1): 19–36 [2024-01-30], S2CID 16520181, doi:10.1007/s00493-008-2140-4, （原始内容 (PDF)于2020-10-11） .
• Diestel, Reinhard, A short proof of Halin's grid theorem, Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 2004, 74: 237–242, MR 2112834, S2CID 124603912, doi:10.1007/BF02941538 .
• Diestel, Reinhard, Graph Theory 3rd, Springer, 2005 [2024-01-30], ISBN 978-3-540-26182-7, （原始内容于2011-07-28） .
• Eppstein, D., Diameter and treewidth in minor-closed graph families, Algorithmica, 2000, 27 (3–4): 275–291, MR 1759751, S2CID 3172160, arXiv:math/9907126  , doi:10.1007/s004530010020 .
• Feige, Uriel; Hajiaghayi, MohammadTaghi; Lee, James R., Improved approximation algorithms for minimum weight vertex separators, SIAM Journal on Computing, 2008, 38 (2): 629–657, CiteSeerX 10.1.1.597.5634  , doi:10.1137/05064299X .
• Fomin, Fedor V.; Todinca, Ioan; Villanger, Yngve, Large induced subgraphs via triangulations and CMSO, SIAM Journal on Computing, 2015, 44 (1): 54–87, S2CID 15880453, arXiv:1309.1559  , doi:10.1137/140964801 .
• Frick, Markus; Grohe, Martin, Deciding first-order properties of locally tree-decomposable structures, Journal of the ACM, 2001, 48 (6): 1184–1206, MR 2143836, S2CID 999472, arXiv:cs/0004007  , doi:10.1145/504794.504798 .
• Fomin, Fedor V.; Lokshtanov, Daniel; Saurabh, Saket; Pilipczuk, Michal; Wrochna, Marcin, Fully polynomial-time parameterized computations for graphs and matrices of low treewidth, ACM Transactions on Algorithms, 2018, 14 (3): 34:1–34:45, S2CID 2144798, arXiv:1511.01379  , doi:10.1145/3186898 .
• Grigoriev, Alexander; Bodlaender, Hans L., Algorithms for graphs embeddable with few crossings per edge, Algorithmica, 2007, 49 (1): 1–11, CiteSeerX 10.1.1.65.5071  , MR 2344391, S2CID 8174422, doi:10.1007/s00453-007-0010-x .
• Halin, Rudolf, S-functions for graphs, Journal of Geometry, 1976, 8 (1–2): 171–186, S2CID 120256194, doi:10.1007/BF01917434 .
• Kao, Ming-Yang (编), Treewidth of graphs, Encyclopedia of Algorithms, Springer: 969, 2008, ISBN 9780387307701, Another long-standing open problem is whether there is a polynomial-time algorithm to compute the treewidth of planar graphs. 
• Korhonen, Tuukka, A Single-Exponential Time 2-Approximation Algorithm for Treewidth, Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, IEEE: 184–192, 2021, S2CID 233240958, arXiv:2104.07463  , doi:10.1109/FOCS52979.2021.00026 .
• Lagergren, Jens, An upper bound on the size of an obstruction, Graph structure theory (Seattle, WA, 1991), Contemporary Mathematics 147, Providence, RI: American Mathematical Society: 601–621, 1993, ISBN 9780821851609, MR 1224734, doi:10.1090/conm/147/01202 .
• Lagergren, Jens, Efficient parallel algorithms for graphs of bounded tree-width, Journal of Algorithms, 1996, 20 (1): 20–44, MR 1368716, doi:10.1006/jagm.1996.0002 .
• Ramachandramurthi, Siddharthan, The structure and number of obstructions to treewidth, SIAM Journal on Discrete Mathematics, 1997, 10 (1): 146–157, MR 1430552, doi:10.1137/S0895480195280010 .
• Reed, Bruce A., Finding approximate separators and computing tree width quickly, Kosaraju, S. Rao; Fellows, Mike; Wigderson, Avi; Ellis, John A. (编), Proceedings of the 24th Annual ACM Symposium on Theory of Computing, May 4-6, 1992, Victoria, British Columbia, Canada, ACM: 221–228, 1992, S2CID 16259988, doi:10.1145/129712.129734   .
• Robertson, Neil; Seymour, Paul D., Graph minors III: Planar tree-width, Journal of Combinatorial Theory, Series B, 1984, 36 (1): 49–64, doi:10.1016/0095-8956(84)90013-3   .
• Robertson, Neil; Seymour, Paul D., Graph minors V: Excluding a planar graph, Journal of Combinatorial Theory, Series B, 1986, 41 (1): 92–114, doi:10.1016/0095-8956(86)90030-4   .
• Robertson, Neil; Seymour, Paul D., Graph Minors XIII: The Disjoint Paths Problem, Journal of Combinatorial Theory, Series B, 1995, 63 (1): 65–110, doi:10.1006/jctb.1995.1006   .
• Robertson, Neil; Seymour, Paul; Thomas, Robin, Quickly excluding a planar graph, Journal of Combinatorial Theory, Series B, 1994, 62 (2): 323–348, MR 1305057, doi:10.1006/jctb.1994.1073   .
• Satyanarayana, A.; Tung, L., A characterization of partial 3-trees, Networks, 1990, 20 (3): 299–322, MR 1050503, doi:10.1002/net.3230200304 .
• Seymour, Paul D.; Thomas, Robin, Graph searching and a min-max theorem for tree-width, Journal of Combinatorial Theory, Series B, 1993, 58 (1): 22–33, doi:10.1006/jctb.1993.1027   .
• Shoikhet, Kirill; Geiger, Dan, A Practical Algorithm for Finding Optimal Triangulations, Kuipers, Benjamin; Webber, Bonnie L. (编), Proceedings of the Fourteenth National Conference on Artificial Intelligence and Ninth Innovative Applications of Artificial Intelligence Conference, AAAI 97, IAAI 97, July 27-31, 1997, Providence, Rhode Island, USA, AAAI Press / The MIT Press: 185–190, 1997 [2024-01-30], （原始内容于2022-02-02） .
• Thorup, Mikkel, All structured programs have small tree width and good register allocation, Information and Computation, 1998, 142 (2): 159–181, doi:10.1006/inco.1997.2697   .
• Korhonen, Tuukka; Lokshtanov, Daniel, An Improved Parameterized Algorithm for Treewidth, 2022, arXiv:2211.07154   [cs.DS] .