樹寬

圖論中，無向圖的樹寬（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 et al. (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 et al. (2016)
${\displaystyle 5k+4}$	${\displaystyle 2^{O(k)}}$	${\displaystyle O(n)}$	Bodlaender et al. (2016)
${\displaystyle k^{2}}$	${\displaystyle O(k^{7})}$	${\displaystyle O(n\log n)}$	Fomin et al. (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 et al. (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].