徑寬

圖論中，圖G的徑分解（path decomposition）是G的「加粗」路徑圖表示，G的徑寬（pathwidth）是衡量形成G的路徑被加粗的程度。更正式地說，徑分解是G的頂點子集序列，使每條邊的端點出現在某一子集中，並使每個頂點都出現在子集連續子序列中，徑寬等於這樣的分解中最大集的大小減一。 徑寬也叫做區間厚度（interval thickness，等於G的區間父圖中的最大團大小減一）、頂點分隔數（vertex separation number）或結點搜索數（node searching number）。

徑寬與徑分解同樹寬、樹分解關係密切，在圖子式理論中起關鍵作用：在圖子式下封閉、不含所有森林的圖族可描述為徑寬有界，子式閉圖族的一般結構理論中出現的「渦」（vortex）的徑寬也有界。徑寬與徑寬有界圖在超大規模集成電路設計、圖繪製、計算語言學等領域也有應用。

計算任意圖的徑寬、甚至精確近似徑寬都是NP困難的。不過，這問題是固定參數可解的：測試圖的徑寬是否為k，耗時與圖的大小呈線性關係，而與k呈上指數關係。另外，對樹之類的特殊圖，徑寬可在多項式時間內算得，而不依賴於k。 對圖的徑分解使用動態規劃，可以將圖算法中很多問題在徑寬有界圖上高效解決。徑分解也可測量樹寬有界圖上動態規劃算法的空間複雜度。

定義

徑寬為2的例圖G，其徑分解寬度為2。圖像下半部是相同的圖與徑分解，添加了顏色以示強調。（本例改編自Bodlaender (1994a)，添加了記號）

Neil Robertson and Paul Seymour （1983）在圖子式系列論文的第一篇中，將圖G的徑分解定義為G的頂點子集$X_{i}$序列，滿足兩條屬性：

1. 對G中每條邊，存在i使邊的兩端點都屬於子集$X_{i}$；
2. $\forall i\leq j\leq k,\ X_{i}\cap X_{k}\subseteq X_{j}.$

第二條性質等價於要求包含任意特定頂點的子集構成整個序列的連續子列。用系列論文後期的話來說，徑分解是樹分解$(X,\ T)$，其中分解的底樹T是路徑圖。 徑分解的寬度與樹分解類似，是${\rm {max}}_{i}|X_{i}|-1$，G的徑寬是G的徑分解的最小寬度。在徑寬的大多數應用中，$X_{i}$的大小減不減一沒什麼差別，主要是為了使路徑圖的徑寬等於1。

其他特徵

如Bodlaender (1998)所描述的，徑寬可用許多等價方法表徵。

粘合序列

徑分解可表述為圖$G_{i}$的序列，找到來自序列中連續圖的頂點對，並將圖粘合在一起，所有粘合的結果就是G。在徑分解的第一個定義中，圖$G_{i}$可看作是集合$X_{i}$的誘導子圖，連續（successive）誘導子圖中的兩頂點被G中相同頂點誘導時，就會被粘在一起；反之，可以把集合$X_{i}$恢復為圖$G_{i}$的頂點集。則徑分解的寬度比某一圖$G_{i}$的最大頂點數少1。

區間厚度

徑寬為2的區間圖，而4個最大團ABC、ACD、CDE、CDF的大小為3。

任意圖G的徑寬等於含G（以G為子圖）的區間圖的最小團數減一。即，對G的每種徑分解，都能找到G的區間子圖；對G的每個區間父圖，都能找到G的徑分解，使分解的寬度比區間圖團數小1。

假設給出了G的徑分解。則可將分解的結點表為直線上的點（按路徑順序），並將每個頂點v表示為以這些點為端點的閉區間。這樣，包含v的徑分解結點就對應v在區間中的代表點。G頂點形成的區間交圖是包含G的區間圖，其最大團由包含代表點的區間集給出，大小比G的徑寬大1。

設G是某區間圖的子圖，團數$p+1$，則G有寬p的徑分解，其結點由區間圖的最大團給出。例如，圖中的區間圖及其區間表示的徑分解有5個結點，分別對應5個最大團ABC、ACD、CDE、CDF、FG；最大團大小為3，這徑分解的寬度為2。 徑寬與區間厚度之間的等價關係同樹寬與弦圖（給定圖是弦圖的子圖）的最小團數（減一）的等價關係非常相似。區間圖是弦圖的特例，弦圖可表為共同樹的子樹的交圖，這類似於區間圖是路徑子徑的交圖。

頂點分隔數

設圖G的頂點是線性有序的。則，G的頂點分隔數是滿足下列條件的最小數s：對頂點v，最多s個頂點在排序中先於v，但有v或更靠後的頂點相鄰。 G的頂點分隔數是G的任意線性排序的最小頂點分隔數。頂點分隔數由Ellis，Sudborough & Turner (1983)定義，等於G的徑寬。 這源於前述的與區間圖團數的等價關係：若G是區間圖I的子圖，並以所有區間端點都分離的方式表示（如圖所示），則I的區間左端點排序的頂點分隔數比I的團數小1。反過來，從G的線性排序可推導出一種區間表示：頂點v的區間左端點是其在排序中的位置，右端點是v在排序中最後一個鄰居的位置。

結點搜索數

圖上的結點搜索策略是追逃對策的一種形式，當中一組搜索者合作追蹤藏在圖中的逃犯。搜索者被置於圖的頂點上，逃犯可能在任意邊上，位置與移動對搜索者不可見。每個回合中，搜索者的部分或全部可從頂點移動到另一頂點（任意移動，不必沿邊），逃犯可以沿不經過搜索者頂點的任意路徑移動。逃犯所在邊的兩端點都被搜索者占據時，就被抓獲。圖的結點搜索數是必然能抓到逃犯的最少搜索者數。如Kirousis & Papadimitriou (1985)所示，圖的結點搜索數等於其區間厚度。搜索者的最優策略是不斷移動搜索者，使他們在連續回合中形成具有最小頂點分隔數的線性排序的分隔集。

界

毛蟲樹，徑寬為1的最大圖。

徑寬為k的n頂點圖至多有$k(n-k+{\frac {k-1}{2}})$條邊，是最大k徑寬圖（即徑寬為k、無論怎樣添加邊都必改變徑寬的圖）的邊數。徑寬為k的最大圖要麼是k徑圖要麼是k毛蟲圖，它們是兩種特殊的k樹。k樹是恰有$n-k$個最大團（含$k+1$個頂點）的弦圖；在本身不是$(k+1)$團的k樹中，每個最大團要麼將圖分隔成多個部分，要麼包含單個葉頂點（只屬於一個最大團的頂點）。k徑圖是至少有兩葉的k樹，k毛蟲圖是可分割維k徑與一組k葉的k樹，其中每片葉還與k徑中的獨立k團相鄰。徑寬為1的最大圖是毛蟲樹。

由於徑分解是樹分解的特例，徑寬不小於樹寬，且不大於割寬，即在圖頂點的最優線性排列中，前後頂點組之間割邊的最小數。這是因為，頂點分隔數即前後頂點組的鄰接數不大於割邊數。出於類似原因，割寬不大於徑寬乘頂點的最大度。

任意n頂點森林都有徑寬$O(\log n)$。例如，對一個森林，總能找到恆定多的頂點，使得去掉它們後形成至多有${\frac {2n}{3}}$個頂點的兩片子森林。如此遞歸地分隔子森林，將分隔頂點置於兩者之間，形成的線性排列具有對數頂點搜索數。此技術用於樹分解時，可知，若n頂點圖G的樹寬為t，則G的徑寬是$O(t\log n)$。由於外平面圖、系列並行圖、哈林圖的樹寬都有界，它們的徑寬最多為對數的。

此外，徑寬還通過線圖，同團寬與割寬有關係。G的邊在其線圖$L(G)$中都有對應的頂點，當G中相應的兩邊有共同端點時，$L(G)$中的兩頂點就是相鄰的。若且唯若圖族的線圖的線性團寬（用鄰接1個新頂點的操作取代了團寬的不交並操作）有界，圖族的徑寬有界。若某3及以上個頂點的連通圖的最大度為3，則其割寬等於線圖的頂點分隔數。

平面圖的徑寬最多與頂點數的平方根成正比。找到具有這種寬度的徑分解，一種方法是（與上述森林的對數寬徑分解類似）用平面分隔定理找到$O({\sqrt {n}})$個頂點的集合，其將圖分隔為至多有${\frac {2n}{3}}$個頂點的兩個子圖，如此遞歸地分隔子圖，最後將兩子圖的遞歸徑分解連接起來。同樣的技術也適用於類似分離器定理成立的任何一類圖。與平面圖一樣，任何固定的子式閉圖族中的圖都有大小為$O({\sqrt {n}})$的分隔子，因此此類圖族中圖的徑寬也是$O({\sqrt {n}})$。對某類平面圖，圖的徑寬與其對偶圖的徑寬必須在一常數因子範圍內，對於雙連通外平面圖與多面體圖，這種形式的邊界是已知的。2連通平面圖的對偶圖的徑寬小於線圖的徑寬。至於在其他情形下，平面圖徑寬與對偶圖徑寬是否總相差某常數因子，仍是未知的。

在某些類的圖中，徑寬與樹寬總相等。已證明的有余圖、置換圖、可比圖之補、區間序的可比圖。

在立方圖中，或更廣義地在任何最大頂點度為3的圖中，徑寬不大於${\frac {n}{6}}+o(n)$，其中n是頂點數。存在徑寬為$0.082n$的立方圖，但如何縮小這下界與上界${\frac {n}{6}}$之間的差距，目前還不得而知。

計算徑分解

確定給定圖的徑寬是否大於k的問題是NP完全的（k也是輸入）。計算任意n頂點圖徑寬的最壞情形的最優時間邊界為$O(2^{n}n^{c})$，c是常數。不過，已經有幾種算法可在徑寬較小、輸入圖類別有限或近似的情形下更高效地計算徑分解。

固定參數可解

徑寬是固定參數可解的：對任意常數k，都可測試徑寬是否大於k，若不大於k，則在線性時間內找到寬k的徑分解。一般來說，這類算法分兩階段運行。第一階段，假設圖的徑寬為k，以找到並非最優的徑分解或樹分解，寬度可作為k的函數而變為約束。第二階段，對這分解運用動態規劃算法，以找到最優分解。然而，已知的這類算法的時間界限是$k^{2}$的指數級，除了最小的k外，都是不切實際的。對於$k=2$的情形，de Fluiter (1997)給出了基於2徑寬圖的結構分解的精確限行時間算法。

特殊圖類

Bodlaender (1994)調查了計算各種特殊圖類的徑寬的複雜性。若圖G是有界度圖、平面圖、有界度平面圖、弦圖、弦多米諾、可比圖之補、二分距離遺傳圖，確定圖G的徑寬是否最大是k的問題仍是NP完全的。對於包含二分距離遺傳圖的圖族（二分圖、弦二分圖、距離遺傳圖、循環圖之類），也是NP完全的。

不過，對於樹與森林，徑寬可在線性時間內算得。對樹寬有界圖族（系列並行圖、外平面圖、哈林圖）、裂圖、弦圖之補、置換圖、余圖、圓弧圖、區間序的可比圖、區間圖，也可在多項式時間內計算出來。這種情形下，徑寬比覆蓋圖的區間表示中所有點的最大區間數小1。

近似算法

將圖的徑寬近似到加常數範圍內，是NP難的。 已知近似率最佳的多項式時間近似算法是$O((\log n)^{3/2})$。 關於計算徑寬的早期近似算法，見Bodlaender 等人 (1992)與Guha (2000)；關於受限圖類的近似計算，見Kloks & Bodlaender (1992)。

圖子式

圖G的子式是由G通過收縮邊、移除邊、移除頂點得到的另一張圖。圖子式有深奧的理論，其中幾個重要結果涉及徑寬。

排除森林

若圖族F對取子式封閉（即F成員的子式還在F中），則由羅伯森–西摩定理，F的特徵是在禁子式有限集X中沒有任何子式。例如，華格納定理指出，平面圖是既沒有完整圖$K_{5}$也沒有完全二分圖$K_{3,\ 3}$作為子式的圖。很多時候，F的性質與X的性質密切相關，此類的第一個結果由Robertson & Seymour (1983)提出，將有界徑寬與禁子式族中森林的存在聯繫起來。具體來說，若存在常數p使F中圖的徑寬不大於p，則稱圖族F具有有界徑寬。那麼，若且唯若F的禁子式集X至少包括一個森林時，子式閉族F具有有界的徑寬。

從一個方向來看，這結果很容易證明：若X不含森林，則「無X子式圖」的徑寬便無界。因為這時，無X子式圖將包含所有森林，特別是包括完美二元樹。而一棵$2k+1$層的完美二元樹的徑寬為k，所以這時無X子式圖的徑寬無解。從另一方向看，若X包含n頂點森林，則無X子式圖的徑寬不大於$n-2$。

徑寬有界的障礙

徑寬為1的圖的禁子式。

徑寬不大於p的性質本身對取子式封閉：若G的徑分解寬度不大於p，則從G中刪去任何邊，同一徑分解仍有效，且可以從G及其徑分解中刪去任意頂點而不增加寬度。同樣，通過合併表示收縮後邊的兩端點的子徑，也可在收縮邊時不增加分解寬度。因此，徑寬至多為p的圖可用排除子式的集合$X_{p}$描述。

雖然$X_{p}$必然包括森林，但並不是說$X_{p}$中的所有圖都是森林：例如，$X_{1}$包含2張圖，一個7頂點樹與三角$K_{3}$。而$X_{p}$中的樹集可以精確描述：它們是$X_{p-1}$中三棵樹通過邊，連接新的根頂點與3棵小樹中任意頂點而形成的樹。例如，$X_{1}$中的7頂點樹就是這樣由$X_{0}$中的2頂點樹（一條邊）組成的。基於這種構造，可以證明$X_{p}$中的禁子式數至少為$(p!)^{2}$。已計算出2徑寬圖的完備禁子式集$X_{2}$，其中包含110個圖。

結構理論

子式閉圖族的圖結構定理指出，對任意圖族F，其中的圖可分解為能嵌入到虧格有界曲面上的圖的團和，且團和的每個分量都有有界多的頂點（apex）與渦（vortex）。這裡的頂點可能與其組分中任何頂點相鄰，渦是徑寬有界圖，粘合到某組分的虧格有界嵌入的面上。渦所嵌入面周圍的頂點的循環排序必須與渦的徑分解相容，即，打破循環、形成線性排序必然產生頂點分隔數有界的排序。這一理論中，徑寬與任意子式閉圖族密切相關，具有重要的算法應用。

應用

超大規模集成電路

超大規模集成電路設計中，頂點分隔問題最初是將電路分為子系統的方法，子系統邊界有少量元件。

Ohtsuki 等人 (1979)使用區間厚度模擬VLSI一維布局所需的軌道數，此布局由網絡系統相互連接的模塊組成。在他們的模型中，頂點代表網，若兩網都連接到同一模塊，就將兩頂點由邊相連；也就是說，若將模塊與網視作超圖的結點與超邊，則由它們形成的圖就是超圖的線圖。這超圖的區間表示與著色描述了沿水平軌道（一種顏色對應一條軌道）系統的網的排列，使模塊可沿軌道以線性順序排列，並連接到相應的網。區間圖都是完美圖，表明這類最佳排列中，所需顏色數等於網圖的區間完備化的團數。

門矩陣布局是一種用於布爾邏輯電路的CMOS VLSI布局。當中，信號沿「線」（垂直線段）傳播，而電路的每個門則由沿水平線段的一系列器件特徵構成。因此，代表門的水平線段須與代表門輸入輸出的線路的垂直線段交叉。與Ohtsuki 等人 (1979)的布局類似，通過計算以線路為頂點，以共享同一門的線對為邊的圖的徑寬，可以找到使排列線路的垂直軌道數最小的布局。這種算法方法也可為可程式邏輯陣列的摺疊問題建模。

圖繪製

徑寬在圖繪製中有多個應用：

• 給定交叉數的最小圖的徑寬受交叉數函數的約束。
• 樹的頂點可畫在多少條平行線上而邊不交（根據對相鄰頂點在線序列上擺放方式的各種自然限制），與樹的徑寬成正比。
• 圖G的k交叉h層繪圖是將G的頂點放置在h條水平線上，邊在其間以單調多邊形路徑排列，使得最多有k處交叉。具有這種繪製的圖的徑寬由h與k的函數約束。於是，h、k為常值時，可在線性時間內確定圖是都具有k交叉h層繪製。
• n頂點、徑寬為p的圖可嵌入3維格$p\times p\times n$，使得邊（表為格點間的直線段）不交。於是，徑寬有界圖具有此種線性體積嵌入。

編譯器設計

高級語言的編譯過程中，徑寬見於重排直線代碼序列（即無控制流分支或循環的代碼）問題，使代碼算得的所有值都可放在暫存器中，而不必溢出到主內存中。這種應用中，我們將待編譯代碼表為有向無環圖，其中結點是代碼的輸入輸出值。這個DAG中，結點x到結點y的邊表示x值是操作了y的輸入之一。此DAG的頂點的拓撲排序表示代碼的有效重排，在給定排序中評估代碼所需的暫存器數由排序的頂點分隔數給出。

對表示暫存器數的任意定值w，可在限行時間內確定一段直線代碼能否重排，以便用不多於w個暫存器求值。若拓撲排序的頂點分隔數最多為w，則所有排序中的最小頂點分隔也不會更大，於是忽略DAG方向形成的無向圖的徑寬不大於w。可用已知的固定參數可解算法計算徑寬，若是，則可在假設w為常數的線性時間內找到無向圖的徑分解。找到徑分解，就可用動態規劃，在線性時間內找到寬w的拓撲排序。

語言學

Kornai & Tuza (1992)描述了徑寬在自然語言處理中的應用。句子被建模為圖，頂點表示詞，邊表示詞之間的關係。例如，若形容詞修飾了名詞，則圖中這兩個詞之間就會有一條邊。Kornai和Tuza認為，由於人類的短時記憶能力有限，這種圖的徑寬一定有界（更具體地說，他們認為是6），否則人類將無法正確解析語言。

指數算法

圖算法中的很多問題都可通過對徑分解進行動態規劃，在徑寬較小的圖上高效解決。例如，若給定n頂點圖G的頂點的線性排序，就有可能在$O(2^{w}n)$的時間內找到G的最大獨立集。在徑寬有界圖上，這種方法會產生以徑寬為參數的固定參數可解算法。這種結果在文獻中不常見，因為已經包含在以樹寬為參數的類似算法；然而，即使在基於樹寬的動態規劃算法中，徑寬也會出現衡量算法空間複雜度的過程中。

同樣的動態規劃方法也可用於徑寬無界圖，產生以指數時間解決無參圖問題的算法。例如，將這種方法與立方圖徑寬為${\frac {n}{6}}+o(n)$的事實相結合，可以發現在立方圖中，最大支配集的構造耗時$O(2^{{\frac {n}{6}}+o(n)})$，比以往方法更快。類似方法還可改進立方圖中最大割與最小支配集問題的指數時間算法，及其他一些NP難優化問題的指數時間算法。

另見

• 箱性
• 割寬
• 樹深
• 退化 (圖論)
• 帶寬 (圖論)

• 斯特拉勒數

參考文獻

• Alon, Noga; Seymour, Paul; Thomas, Robin, A separator theorem for graphs with an excluded minor and its applications, Proc. 22nd ACM Symp. on Theory of Computing (STOC 1990): 293–299, 1990, ISBN 0897913612, S2CID 17521329, doi:10.1145/100216.100254  .
• Amini, Omid; Huc, Florian; Pérennes, Stéphane, On the path-width of planar graphs, SIAM Journal on Discrete Mathematics, 2009, 23 (3): 1311–1316, doi:10.1137/060670146 .
• Arnborg, Stefan, Efficient algorithms for combinatorial problems on graphs with bounded decomposability – A survey, BIT, 1985, 25 (1): 2–23, S2CID 122263659, doi:10.1007/BF01934985 .
• Arnborg, Stefan; Corneil, Derek G.; Proskurowski, Andrzej, Complexity of finding embeddings in a k-tree, SIAM Journal on Algebraic and Discrete Methods, 1987, 8 (2): 277–284, doi:10.1137/0608024 .
• Aspvall, Bengt; Proskurowski, Andrzej; Telle, Jan Arne, Memory requirements for table computations in partial k-tree algorithms, Algorithmica, 2000, 27 (3): 382–394, S2CID 9690525, doi:10.1007/s004530010025 .
• Berge, Claude, Some classes of perfect graphs, Graph Theory and Theoretical Physics, New York: Academic Press: 155–165, 1967 .
• Bienstock, Dan; Robertson, Neil; Seymour, Paul; Thomas, Robin, Quickly excluding a forest, Journal of Combinatorial Theory, Series B, 1991, 52 (2): 274–283, doi:10.1016/0095-8956(91)90068-U  .
• Björklund, Andreas; Husfeldt, Thore, Exact algorithms for exact satisfiability and number of perfect matchings, Algorithmica, 2008, 52 (2): 226–249, S2CID 37693881, doi:10.1007/s00453-007-9149-8 .
• Bodlaender, Hans L., A tourist guide through treewidth, Dassow, Jürgen; Kelemenová, Alisa (編), Developments in Theoretical Computer Science (Proc. 7th International Meeting of Young Computer Scientists, Smolenice, 16–20 November 1992), Topics in Computer Mathematics 6, Gordon and Breach: 1–20, 1994 .
• Bodlaender, Hans L. A tourist guide through treewidth. Acta Cybernetica. 1994a, 11: 1–2. 
• Bodlaender, Hans L., A linear-time algorithm for finding tree-decompositions of small treewidth, SIAM Journal on Computing, 1996, 25 (6): 1305–1317, doi:10.1137/S0097539793251219, hdl:1874/16670  .
• 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.; Fomin, Fedor V., Approximation of pathwidth of outerplanar graphs, Journal of Algorithms, 2002, 43 (2): 190–200, doi:10.1016/S0196-6774(02)00001-9 .
• Bodlaender, Hans L.; Gilbert, John R.; Hafsteinsson, Hjálmtýr; Kloks, Ton, Approximating treewidth, pathwidth, and minimum elimination tree height, Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science 570: 1–12, 1992, ISBN 978-3-540-55121-8, doi:10.1007/3-540-55121-2_1, hdl:1874/17927  .
• Bodlaender, Hans L.; Gustedt, Jens; Telle, Jan Arne, Linear-time register allocation for a fixed number of registers, Proc. 9th ACM–SIAM Symposium on Discrete Algorithms (SODA '98) (PDF): 574–583, 1998 .
• Bodlaender, Hans L.; Kloks, Ton, Efficient and constructive algorithms for the pathwidth and treewidth of graphs, Journal of Algorithms, 1996, 21 (2): 358–402, doi:10.1006/jagm.1996.0049, hdl:1874/16538  .
• Bodlaender, Hans L.; Kloks, Ton; Kratsch, Dieter, Treewidth and pathwidth of permutation graphs, Proc. 20th International Colloquium on Automata, Languages and Programming (ICALP 1993), Lecture Notes in Computer Science 700, Springer-Verlag: 114–125, 1993, ISBN 978-3-540-56939-8, doi:10.1007/3-540-56939-1_66, hdl:1874/16657  .
• Bodlaender, Hans L.; Möhring, Rolf H., The pathwidth and treewidth of cographs, Proc. 2nd Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science 447, Springer-Verlag: 301–309, 1990, ISBN 978-3-540-52846-3, doi:10.1007/3-540-52846-6_99, hdl:1874/16625  .
• Cattell, Kevin; Dinneen, Michael J.; Fellows, Michael R., A simple linear-time algorithm for finding path-decompositions of small width, Information Processing Letters, 1996, 57 (4): 197–203, S2CID 2442557, arXiv:math/9410211 , doi:10.1016/0020-0190(95)00190-5 .
• Coudert, David; Huc, Florian; Mazauric, Dorian, A Distributed Algorithm for Computing the Node Search Number in Trees (PDF), Algorithmica, 2012, 63 (1): 158–190, doi:10.1007/s00453-011-9524-3 .
• Coudert, David; Huc, Florian; Sereni, Jean-Sébastien, Pathwidth of outerplanar graphs (PDF), Journal of Graph Theory, 2007, 55 (1): 27–41, doi:10.1002/jgt.20218 .
• Diestel, Reinhard, Graph Minors I: a short proof of the path-width theorem, Combinatorics, Probability and Computing, 1995, 4 (1): 27–30, doi:10.1017/S0963548300001450 .
• Diestel, Reinhard; Kühn, Daniela, Graph minor hierarchies, Discrete Applied Mathematics, 2005, 145 (2): 167–182, doi:10.1016/j.dam.2004.01.010  .
• Demaine, Erik D.; Hajiaghayi, MohammadTaghi; Kawarabayashi, Ken-ichi, Algorithmic graph minor theory: decomposition, approximation, and coloring, Proc. 46th IEEE Symposium on Foundations of Computer Science (FOCS 2005): 637–646, 2005, ISBN 0-7695-2468-0, S2CID 13238254, doi:10.1109/SFCS.2005.14 .
• Downey, Rod G.; Fellows, Michael R., Parameterized Complexity, Springer-Verlag, 1999, ISBN 0-387-94883-X .
• Dujmović, V.; Fellows, M.R.; Kitching, M.; Liotta, G.; McCartin, C.; Nishimura, N.; Ragde, P.; Rosamond, F.; Whitesides, S.; Wood, David R., On the parameterized complexity of layered graph drawing, Algorithmica, 2008, 52 (2): 267–292, S2CID 2298634, doi:10.1007/s00453-007-9151-1 .
• Dujmović, Vida; Morin, Pat; Wood, David R., Path-width and three-dimensional straight-line grid drawings of graphs (PDF), Proc. 10th International Symposium on Graph Drawing (GD 2002), Lecture Notes in Computer Science 2528, Springer-Verlag: 42–53, 2003 .
• Ellis, J. A.; Sudborough, I. H.; Turner, J. S., Graph separation and search number, Proc. 1983 Allerton Conf. on Communication, Control, and Computing, 1983 . As cited by Monien & Sudborough (1988).
• Ellis, J. A.; Sudborough, I. H.; Turner, J. S., The vertex separation and search number of a tree, Information and Computation, 1994, 113 (1): 50–79, doi:10.1006/inco.1994.1064  .
• Feige, Uriel; Hajiaghayi, Mohammadtaghi; Lee, James R., Improved approximation algorithms for minimum-weight vertex separators, Proc. 37th ACM Symposium on Theory of Computing (STOC 2005): 563–572, 2005, ISBN 1581139608, S2CID 14097859, doi:10.1145/1060590.1060674 .
• Fellows, Michael R.; Langston, Michael A., On search decision and the efficiency of polynomial-time algorithms, Proc. 21st ACM Symposium on Theory of Computing: 501–512, 1989, ISBN 0897913078, S2CID 1854173, doi:10.1145/73007.73055  .
• Ferreira, Afonso G.; Song, Siang W., Achieving optimality for gate matrix layout and PLA folding: a graph theoretic approach, Proc. 1st Latin American Symposium on Theoretical Informatics (LATIN '92), Lecture Notes in Computer Science 583, Springer-Verlag: 139–153, 1992, ISBN 3-540-55284-7, doi:10.1007/BFb0023825, hdl:10068/43314  .
• de Fluiter, Babette, Algorithms for Graphs of Small Treewidth (PDF), Ph.D. thesis, Utrecht University, 1997 [2010-05-06], ISBN 90-393-1528-0, （原始內容 (PDF)存檔於2011-07-24） .
• Fomin, Fedor V., Pathwidth of planar and line graphs, Graphs and Combinatorics, 2003, 19 (1): 91–99, S2CID 43123449, doi:10.1007/s00373-002-0490-z .
• Fomin, Fedor V.; Høie, Kjartan, Pathwidth of cubic graphs and exact algorithms, Information Processing Letters, 2006, 97 (5): 191–196, doi:10.1016/j.ipl.2005.10.012 .
• Fomin, Fedor V.; Kratsch, Dieter; Todinca, Ioan; Villanger, Yngve, Exact algorithms for treewidth and minimum fill-in, SIAM Journal on Computing, 2008, 38 (3): 1058–1079, doi:10.1137/050643350, hdl:1956/1151  .
• Fomin, Fedor V.; Thilikos, Dimitrios M., On self duality of pathwidth in polyhedral graph embeddings, Journal of Graph Theory, 2007, 55 (1): 42–54, doi:10.1002/jgt.20219 .
• Garbe, Renate, Tree-width and path-width of comparability graphs of interval orders, Proc. 20th International Workshop Graph-Theoretic Concepts in Computer Science (WG'94), Lecture Notes in Computer Science 903, Springer-Verlag: 26–37, 1995, ISBN 978-3-540-59071-2, doi:10.1007/3-540-59071-4_35 .
• Golovach, P. A., The cutwidth of a graph and the vertex separation number of the line graph, Discrete Mathematics and Applications, 1993, 3 (5): 517–522, S2CID 120745961, doi:10.1515/dma.1993.3.5.517 .
• Guha, Sudipto, Nested graph dissection and approximation algorithms, Proc. 41st IEEE Symposium on Foundations of Computer Science (FOCS 2000): 126, 2000, ISBN 0-7695-0850-2, S2CID 9854056, doi:10.1109/SFCS.2000.892072 .
• Gurski, Frank; Wanke, Egon, Line graphs of bounded clique-width, Discrete Mathematics, 2007, 307 (22): 2734–2754, doi:10.1016/j.disc.2007.01.020  .
• Gustedt, Jens, On the pathwidth of chordal graphs, Discrete Applied Mathematics, 1993, 45 (3): 233–248, doi:10.1016/0166-218X(93)90012-D  .
• Habib, Michel; Möhring, Rolf H., Treewidth of cocomparability graphs and a new order-theoretic parameter, Order, 1994, 11 (1): 47–60, S2CID 2648030, doi:10.1007/BF01462229 .
• Hliněny, Petr, Crossing-number critical graphs have bounded path-width, Journal of Combinatorial Theory, Series B, 2003, 88 (2): 347–367, doi:10.1016/S0095-8956(03)00037-6  .
• Kashiwabara, T.; Fujisawa, T., NP-completeness of the problem of finding a minimum-clique-number interval graph containing a given graph as a subgraph, Proc. International Symposium on Circuits and Systems: 657–660, 1979 .
• Kinnersley, Nancy G., The vertex separation number of a graph equals its path-width, Information Processing Letters, 1992, 42 (6): 345–350, doi:10.1016/0020-0190(92)90234-M  .
• Kinnersley, Nancy G.; Langston, Michael A., Obstruction set isolation for the gate matrix layout problem, Discrete Applied Mathematics, 1994, 54 (2–3): 169–213, doi:10.1016/0166-218X(94)90021-3  .
• Kirousis, Lefteris M.; Papadimitriou, Christos H., Interval graphs and searching (PDF), Discrete Mathematics, 1985, 55 (2): 181–184, doi:10.1016/0012-365X(85)90046-9 , （原始內容 (PDF)存檔於2011-07-21） .
• Kloks, Ton; Bodlaender, Hans L., Approximating treewidth and pathwidth of some classes of perfect graphs, Proc. 3rd International Symposium on Algorithms and Computation (ISAAC'92), Lecture Notes in Computer Science 650, Springer-Verlag: 116–125, 1992, ISBN 978-3-540-56279-5, doi:10.1007/3-540-56279-6_64, hdl:1874/16672  .
• Kloks, T.; Bodlaender, H.; Müller, H.; Kratsch, D., Computing treewidth and minimum fill-in: all you need are the minimal separators, Proc. 1st European Symposium on Algorithms (ESA'93) (Lecture Notes in Computer Science) 726, Springer-Verlag: 260–271, 1993, doi:10.1007/3-540-57273-2_61 .
• Kloks, Ton; Kratsch, Dieter; Müller, H., Dominoes, Proc. 20th International Workshop Graph-Theoretic Concepts in Computer Science (WG'94), Lecture Notes in Computer Science 903, Springer-Verlag: 106–120, 1995, ISBN 978-3-540-59071-2, doi:10.1007/3-540-59071-4_41 .
• Kneis, Joachim; Mölle, Daniel; Richter, Stefan; Rossmanith, Peter, Algorithms based on the treewidth of sparse graphs, Proc. 31st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2005), Lecture Notes in Computer Science 3787, Springer-Verlag: 385–396, 2005, ISBN 978-3-540-31000-6, doi:10.1007/11604686_34 .
• Korach, Ephraim; Solel, Nir, Tree-width, path-width, and cutwidth, Discrete Applied Mathematics, 1993, 43 (1): 97–101, doi:10.1016/0166-218X(93)90171-J  .
• Kornai, András; Tuza, Zsolt, Narrowness, path-width, and their application in natural language processing, Discrete Applied Mathematics, 1992, 36 (1): 87–92, doi:10.1016/0166-218X(92)90208-R  .
• Lengauer, Thomas, Black-white pebbles and graph separation, Acta Informatica, 1981, 16 (4): 465–475, S2CID 19415148, doi:10.1007/BF00264496 .
• Lopez, Alexander D.; Law, Hung-Fai S., A dense gate matrix layout method for MOS VLSI, IEEE Transactions on Electron Devices, 1980, 27 (8): 1671–1675, Bibcode:1980ITED...27.1671L, S2CID 64469353, doi:10.1109/T-ED.1980.20086, Also in the joint issue, IEEE Journal of Solid-State Circuits 15 (4): 736–740, 1980 .
• Miller, George A., The Magical Number Seven, Plus or Minus Two, Psychological Review, 1956, 63 (2): 81–97, PMID 13310704, doi:10.1037/h0043158, hdl:11858/00-001M-0000-002C-4646-B  .
• Möhring, Rolf H., Graph problems related to gate matrix layout and PLA folding, Tinhofer, G.; Mayr, E.; Noltemeier, H.; et al (編), Computational Graph Theory, Computing Supplementum 7, Springer-Verlag: 17–51, 1990, ISBN 3-211-82177-5 .
• Monien, B.; Sudborough, I. H., Min cut is NP-complete for edge weighted trees, Theoretical Computer Science, 1988, 58 (1–3): 209–229, doi:10.1016/0304-3975(88)90028-X  .
• Ohtsuki, Tatsuo; Mori, Hajimu; Kuh, Ernest S.; Kashiwabara, Toshinobu; Fujisawa, Toshio, One-dimensional logic gate assignment and interval graphs, IEEE Transactions on Circuits and Systems, 1979, 26 (9): 675–684, doi:10.1109/TCS.1979.1084695 .
• Peng, Sheng-Lung; Ho, Chin-Wen; Hsu, Tsan-sheng; Ko, Ming-Tat; Tang, Chuan Yi, A linear-time algorithm for constructing an optimal node-search strategy of a tree, Proc. 4th Int. Conf. Computing and Combinatorics (COCOON'98), Lecture Notes in Computer Science 1449, Springer-Verlag: 197–205, 1998 .
• Proskurowski, Andrzej; Telle, Jan Arne, Classes of graphs with restricted interval models (PDF), Discrete Mathematics and Theoretical Computer Science, 1999, 3: 167–176 .
• Robertson, Neil; Seymour, Paul, Graph minors. I. Excluding a forest, Journal of Combinatorial Theory, Series B, 1983, 35 (1): 39–61, doi:10.1016/0095-8956(83)90079-5  .
• Robertson, Neil; Seymour, Paul, Graph minors. XVI. Excluding a non-planar graph, Journal of Combinatorial Theory, Series B, 2003, 89 (1): 43–76, doi:10.1016/S0095-8956(03)00042-X  .
• Robertson, Neil; Seymour, Paul D., Graph Minors. XX. Wagner's conjecture, Journal of Combinatorial Theory, Series B, 2004, 92 (2): 325–357, doi:10.1016/j.jctb.2004.08.001  .
• Scheffler, Petra, A linear algorithm for the pathwidth of trees, Bodendiek, R.; Henn, R. (編), Topics in Combinatorics and Graph Theory, Physica-Verlag: 613–620, 1990 .
• Scheffler, Petra, Optimal embedding of a tree into an interval graph in linear time, Nešetřil, Jaroslav; Fiedler, Miroslav (編), Fourth Czechoslovakian Symposium on Combinatorics, Graphs and Complexity, Elsevier, 1992 .
• Skodinis, Konstantin, Computing optimal linear layouts of trees in linear time, Proc. 8th European Symposium on Algorithms (ESA 2000), Lecture Notes in Computer Science 1879, Springer-Verlag: 403–414, 2000, ISBN 978-3-540-41004-1, doi:10.1007/3-540-45253-2_37 .
• Skodinis, Konstantin, Construction of linear tree-layouts which are optimal with respect to vertex separation in linear time, Journal of Algorithms, 2003, 47 (1): 40–59, doi:10.1016/S0196-6774(02)00225-0 .
• Suchan, Karol; Todinca, Ioan, Pathwidth of circular-arc graphs, Proc. 33rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2007), Lecture Notes in Computer Science 4769, Springer-Verlag: 258–269, 2007, doi:10.1007/978-3-540-74839-7_25 .
• Suderman, Matthew, Pathwidth and layered drawings of trees (PDF), International Journal of Computational Geometry and Applications, 2004, 14 (3): 203–225, doi:10.1142/S0218195904001433, （原始內容 (PDF)存檔於2003-05-03） .
• Takahashi, Atsushi; Ueno, Shuichi; Kajitani, Yoji, Minimal acyclic forbidden minors for the family of graphs with bounded path-width, Discrete Mathematics, 1994, 127 (1–3): 293–304, doi:10.1016/0012-365X(94)90092-2  .