ในทฤษฎีกราฟ treewidth ของกราฟแบบไม่มีทิศทางคือ จำนวน เต็มที่ระบุอย่างไม่เป็นทางการว่ากราฟนั้นอยู่ห่างจากการเป็นต้นไม้มาก น้อยเพียงใด treewidth ที่เล็กที่สุดคือ 1 กราฟที่มี treewidth เท่ากับ 1 คือต้นไม้และป่าตัวอย่างของกราฟที่มี treewidth ไม่เกิน 2 คือกราฟแบบอนุกรมขนานกราฟสูงสุดที่มี treewidth เท่ากับkเรียกว่าk -treeและกราฟที่มี treewidth ไม่เกินkเรียกว่าpartial k -tree [ ^{1 ] ตระกูล}กราฟอื่นๆ ที่ได้รับการศึกษาอย่างดีหลายตระกูลก็มี treewidth ที่จำกัดเช่นกัน

Treewidth สามารถนิยามอย่างเป็นทางการได้หลายวิธีที่เทียบเท่ากัน ได้แก่ ในแง่ของขนาดของเซตจุดยอดที่ใหญ่ที่สุดในการแยกส่วนต้นไม้ของกราฟ ในแง่ของขนาดของกลุ่มจุดยอด ที่ใหญ่ที่สุด ในการเติมเต็มแบบคอร์ ดัล ของกราฟ ในแง่ของลำดับสูงสุดของที่หลบภัยที่อธิบายกลยุทธ์สำหรับ เกม ไล่ล่า-หลบหนีบนกราฟ หรือในแง่ของลำดับสูงสุดของbrambleซึ่งเป็นกลุ่มของกราฟย่อยที่เชื่อมต่อกันและสัมผัสกันทั้งหมด

Treewidth มักถูกใช้เป็นพารามิเตอร์ใน การวิเคราะห์ ความซับซ้อนแบบพารามิเตอร์ของอัลกอริธึมกราฟอัลกอริธึมหลายตัวที่เป็นปัญหาNP-hardสำหรับกราฟทั่วไป จะง่ายขึ้นเมื่อ treewidth ถูกจำกัดด้วยค่าคงที่

แนวคิดเรื่อง treewidth เดิมทีได้รับการแนะนำโดย Umberto Bertelè และ Francesco Brioschi ( 1972 ) ภายใต้ชื่อมิติต่อมาได้รับการค้นพบใหม่โดยRudolf Halin  ( 1976 ) โดยอิงจากคุณสมบัติที่มันมีร่วมกับพารามิเตอร์กราฟอื่น นั่นคือจำนวน Hadwigerต่อมาได้รับการค้นพบใหม่อีกครั้งโดยNeil RobertsonและPaul Seymour  ( 1984 ) และได้รับการศึกษาโดยผู้เขียนคนอื่นๆ อีกมากมายตั้งแต่นั้นมา^{[ 2 ]}

การแยกโครงสร้างต้นไม้ของกราฟคือต้นไม้ที่แต่ละโหนดเชื่อมโยงกับเซตย่อยของจุดยอดที่เรียกว่า "ถุง" (คำว่าโหนดใช้เพื่ออ้างถึงจุดยอดของกราฟเพื่อหลีกเลี่ยงความสับสนกับจุดยอดของกราฟ) ถุงเหล่านี้ต้องมีคุณสมบัติดังต่อไปนี้: ^{[ 3 ]}${\displaystyle G=(V,E)}$${\displaystyle T}$${\displaystyle T}$${\displaystyle G}$${\displaystyle X_{1},\dots X_{t}}$

1. จุดยอดแต่ละจุดในกราฟจะถูกบรรจุอยู่ในถุงอย่างน้อยหนึ่งถุง:${\displaystyle \textstyle \bigcup _{i}X_{i}=V}$
2. ถ้าทั้งถุงและต่างก็มีจุดยอดแล้วถุงทั้งหมดที่เกี่ยวข้องกับโหนดในเส้นทาง (ที่ไม่ซ้ำกัน) ระหว่างและก็จะมีจุดยอดนั้นด้วยเช่นกัน หรือกล่าวอีกนัยหนึ่ง ถุงที่มีจุดยอดจะเกี่ยวข้องกับซับทรีที่เชื่อมต่อกันของ${\displaystyle X_{i}}$${\displaystyle X_{j}}$${\displaystyle v}$${\displaystyle X_{k}}$${\displaystyle T}$${\displaystyle X_{i}}$${\displaystyle X_{j}}$${\displaystyle v}$${\displaystyle v}$${\displaystyle T}$
3. สำหรับทุกขอบในกราฟ จะมีอย่างน้อยหนึ่งถุงที่บรรจุทั้งและนั่นคือ จุดยอดจะอยู่ติดกันในกราฟก็ต่อเมื่อต้นไม้ย่อยที่สอดคล้องกันมีโหนดร่วมกัน (อย่างไรก็ตาม จุดยอดสองจุดอาจอยู่ในถุงเดียวกันได้โดยไม่จำเป็นต้องอยู่ติดกัน)${\displaystyle (v,w)}$${\displaystyle X_{i}}$${\displaystyle v}$${\displaystyle w}$

ความกว้างของโครงสร้างต้นไม้แบบแยกส่วน คือ ขนาดของกลุ่มที่ใหญ่ที่สุดลบด้วยหนึ่ง ความกว้างของต้นไม้ (treewidth)ของกราฟคือ ความกว้างขั้นต่ำสุดในบรรดาโครงสร้างต้นไม้แบบแยกส่วนที่เป็นไปได้ทั้งหมดในนิยามนี้ ขนาดของเซตที่ใหญ่ที่สุดจะถูกลดลงหนึ่งเพื่อให้ความกว้างของต้นไม้เท่ากับหนึ่ง ${\displaystyle X_{i}}$${\displaystyle \ชื่อผู้ดำเนินการ {tw} (G)}$${\displaystyle G}$${\displaystyle G}$

ในทำนองเดียวกัน ความกว้างของต้นไม้ของกราฟนี้จะน้อยกว่าขนาดของกลุ่ม ที่ใหญ่ที่สุด ในกราฟคอร์ดัลที่มีจำนวนกลุ่มน้อยที่สุด อยู่หนึ่ง ค่า กราฟคอร์ดัลที่มีขนาดกลุ่มนี้สามารถหาได้โดยการเพิ่มขอบระหว่างจุดยอดสองจุดทุก ๆ จุด ซึ่งอย่างน้อยหนึ่งถุงจะบรรจุจุดยอดทั้งสองนั้นไว้ ${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$

ความกว้างของต้นไม้ (treewidth) อาจถูกกำหนดลักษณะในแง่ของ จุดหลบภัย ( haven ) ซึ่งเป็นฟังก์ชันที่อธิบายกลยุทธ์การหลบหลีกสำหรับ เกม ไล่ล่า-หลบหลีกที่กำหนดไว้บนกราฟ กราฟจะมีความกว้างของต้นไม้ก็ต่อเมื่อมีจุดหลบภัยที่มีลำดับแต่ไม่มีลำดับที่สูงกว่า โดยที่จุดหลบภัย ที่มีลำดับ เป็นฟังก์ชันที่แมปแต่ละเซต ของ จุดยอดไม่เกินใน ไปยังส่วนประกอบที่เชื่อมต่อกันของและเป็นไปตาม คุณสมบัติความเป็นเอกภาค (monotonicity property) ที่ว่าเมื่อใดก็ตามที่ ${\displaystyle G}$${\displaystyle k}$${\displaystyle k+1}$${\displaystyle k+1}$${\displaystyle \beta }$${\displaystyle X}$${\displaystyle k}$${\displaystyle G}$${\displaystyle G\setminus X}$${\displaystyle \beta (Y)\subseteq \beta (X)}$${\displaystyle X\subset Y}$

ลักษณะเฉพาะที่คล้ายกันนี้สามารถทำได้โดยใช้bramblesซึ่งเป็นตระกูลของกราฟย่อยที่เชื่อมต่อกันซึ่งสัมผัสกันทั้งหมด (หมายความว่าพวกมันมีจุดยอดร่วมกันหรือเชื่อมต่อกันด้วยขอบ) ^{[ 4 ]}ลำดับของ bramble คือเซตการกระทบ ที่เล็กที่สุด สำหรับตระกูลของกราฟย่อย และ treewidth ของกราฟจะน้อยกว่าลำดับสูงสุดของ bramble หนึ่ง

กราฟสมบูรณ์ ทุก กราฟ จะมี treewidth ซึ่งเห็นได้ชัดเจนที่สุดโดยใช้คำจำกัดความของ treewidth ในแง่ของกราฟคอร์ดัล : กราฟสมบูรณ์เป็นกราฟคอร์ดัลอยู่แล้ว และการเพิ่มขอบมากขึ้นจะไม่สามารถลดขนาดของกลุ่มที่ใหญ่ที่สุดได้ ${\displaystyle K_{n}}$${\displaystyle n-1}$

กราฟเชื่อมต่อที่มีจุดยอดอย่างน้อยสองจุดจะมีค่า treewidth เท่ากับ 1 ก็ต่อเมื่อมันเป็นกราฟต้นไม้ กราฟต้นไม้จะมีค่า treewidth เท่ากับ 1 ด้วยเหตุผลเดียวกับกราฟสมบูรณ์ (กล่าวคือ มันเป็นกราฟคอร์ดัล และมีขนาดคลิกสูงสุดสอง) ในทางกลับกัน ถ้ากราฟมีวัฏจักรการเติมเต็มแบบคอร์ดัล ทุกแบบ ของกราฟจะประกอบด้วยสามเหลี่ยมอย่างน้อยหนึ่งรูปที่ประกอบด้วยจุดยอดสามจุดที่อยู่ติดกันของวัฏจักร ซึ่งจะทำให้ค่า treewidth ของกราฟนั้นอย่างน้อยเท่ากับ 2

สำหรับค่าคงที่ที่กำหนดไว้กราฟที่มี treewidth ไม่เกินจะเรียกว่า partial -trees ตระกูลกราฟอื่นๆ ที่มี treewidth จำกัด ได้แก่cactus graphs , pseudoforests , series–parallel graphs , outerplanar graphs , Halin graphsและApollonian networks [ ^{5 ] กราฟ} ควบคุม การไหลที่เกิดขึ้นในการคอมไพล์โปรแกรมที่มีโครงสร้าง ก็มี treewidth จำกัดเช่นกัน ซึ่งช่วยให้ สามารถดำเนินการบางอย่างได้อย่างมีประสิทธิภาพเช่นการจัดสรรรี จิสเตอร์ ^{[ 6 ]}${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$

กราฟระนาบไม่มี treewidth ที่จำกัด เนื่องจากกราฟกริดเป็นกราฟระนาบที่มี treewidth เท่ากับดังนั้น หากเป็นตระกูลกราฟปิดไมเนอร์ที่มี treewidth ที่จำกัด จะไม่สามารถรวมกราฟระนาบทั้งหมดได้ ในทางกลับกัน หากกราฟระนาบบางกราฟไม่สามารถเกิดขึ้นเป็นไมเนอร์สำหรับกราฟในตระกูลแล้วจะมีค่าคงที่เช่นนั้น กราฟทั้งหมดในจะมี treewidth ไม่เกินนั่นคือ เงื่อนไขสามข้อต่อไปนี้เทียบเท่ากัน: ^{[ 7 ]}${\displaystyle n\times n}$${\displaystyle n}$${\displaystyle F}$${\displaystyle F}$${\displaystyle k}$${\displaystyle F}$${\displaystyle k}$

1. ${\displaystyle F}$เป็นตระกูลของกราฟที่มีความกว้างของต้นไม้จำกัดและปิดในระดับไมเนอร์
2. หนึ่งในคุณสมบัติย่อยต้องห้ามจำนวนจำกัดที่เป็นลักษณะเฉพาะคือคุณสมบัติเชิงระนาบ${\displaystyle F}$
3. ${\displaystyle F}$เป็นตระกูลกราฟปิดย่อยที่ไม่รวมถึงกราฟระนาบทั้งหมด

สำหรับค่าจำกัดทุกค่าของกราฟที่มี treewidth ไม่เกินสามารถระบุลักษณะได้ด้วยเซตจำกัดของไมเนอร์ต้องห้าม (กล่าวคือ กราฟใดๆ ที่มี treewidth มากกว่าจะมีกราฟอย่างน้อยหนึ่งกราฟในเซตนั้นเป็นไมเนอร์) แต่ละเซตของไมเนอร์ต้องห้ามเหล่านี้จะมีกราฟระนาบอย่างน้อยหนึ่งกราฟ ${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$

• สำหรับ ไมเนอร์ต้องห้ามที่ไม่ซ้ำกันคือ กราฟวงจร 3 จุดยอด^{[ 5 ]}${\displaystyle k=1}$
• สำหรับ ไมเนอร์ต้องห้ามที่ไม่ซ้ำกันคือ กราฟสมบูรณ์ 4 จุดยอด^{[ 5 ]}${\displaystyle k=2}$${\displaystyle K_{4}}$
• สำหรับมีไมเนอร์ต้องห้ามสี่อย่าง ได้แก่กราฟของทรงแปดเหลี่ยมกราฟปริซึมห้าเหลี่ยมและกราฟวากเนอร์ ในจำนวนนี้ กราฟทรงหลายเหลี่ยมสอง กราฟ เป็นกราฟระนาบ^{[ 8 ]}${\displaystyle k=3}$${\displaystyle K_{5}}$

สำหรับค่าที่มากขึ้นของจำนวนไมเนอร์ที่ต้องห้ามจะเพิ่มขึ้นอย่างน้อยก็เร็วเท่ากับฟังก์ชันเลขชี้กำลังของ[ ^{9 ] อย่างไรก็ตาม}ขอบเขตบนที่ทราบเกี่ยวกับขนาดและจำนวนของไมเนอร์ที่ต้องห้ามนั้นสูงกว่าขอบเขตล่างนี้มาก^{[ 10 ]}${\displaystyle k}$${\displaystyle {\sqrt {k}}}$

เป็นการยากที่จะระบุว่ากราฟที่กำหนดมี treewidth ไม่เกินตัวแปรที่กำหนด หรือ ไม่^{[ 11 ]} อย่างไรก็ตาม เมื่อเป็นค่าคงที่ใดๆ กราฟที่มี treewidth สามารถรับรู้ได้ และสามารถสร้างการแยกส่วน tree width สำหรับกราฟเหล่านั้นได้ในเวลาเชิงเส้น^{[ 12 ]}การพึ่งพาเวลาของอัลกอริทึมนี้ต่อเป็นแบบเลขชี้กำลัง ${\displaystyle {\mathsf {NP}}}$${\displaystyle G}$${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$

เนื่องจากค่า treewidth มีบทบาทสำคัญในหลายสาขา จึงมีการพัฒนาอัลกอริทึมทั้งในเชิงปฏิบัติและเชิงทฤษฎีเพื่อคำนวณค่า treewidth ของกราฟ ขึ้นอยู่กับแอปพลิเคชันที่ใช้งาน เราอาจเลือกอัตราส่วนการประมาณค่า ที่ดีกว่า หรือความสัมพันธ์ที่ดีกว่าระหว่างเวลาในการทำงานกับขนาดของข้อมูลนำเข้าหรือค่า treewidth ตารางด้านล่างแสดงภาพรวมของอัลกอริทึมคำนวณ treewidth บางส่วน โดยที่คือค่า treewidth และคือจำนวนจุดยอดของกราฟนำเข้าแต่ละอัลกอริทึมจะให้ผลลัพธ์เป็นโครงสร้างต้นไม้ที่มีความกว้างตามที่ระบุในคอลัมน์ Approximation ในเวลา ตัวอย่างเช่น อัลกอริทึมของBodlaender (1996)ในเวลาจะสร้างโครงสร้างต้นไม้ของกราฟนำเข้าที่มีความกว้างไม่เกินหรือรายงานว่าค่า treewidth ของมากกว่าในเวลา ในทำนองเดียวกัน อัลกอริทึมของBodlaender et al. (2016) ในเวลาจะสร้างโครงสร้างต้นไม้ของกราฟนำเข้าที่มีความกว้างไม่เกินหรือรายงานว่าค่า treewidth ของมากกว่า ในเวลาKorhonen (2021)ปรับปรุงความกว้างของการแยกส่วนให้ใช้เวลาการทำงานเท่าเดิม ${\displaystyle k}$${\displaystyle n}$${\displaystyle G}$${\displaystyle f(k)\cdot g(n)}$${\displaystyle 2^{O(k^{3})}\cdot n}$${\displaystyle G}$${\displaystyle k}$${\displaystyle G}$${\displaystyle k}$${\displaystyle 2^{O(k)}\cdot n}$${\displaystyle G}$${\displaystyle 5k+4}$${\displaystyle G}$${\displaystyle k}$${\displaystyle 2k+1}$

การประมาณค่า	ฟ ( k )	g ( n )	อ้างอิง
ที่แน่นอน	${\displaystyle 1}$	${\displaystyle O(n^{k+2})}$	อาร์นบอร์ก, คอร์เนล และ โพรสคูรอฟสกี (1987)
${\displaystyle 4k+3}$	${\displaystyle O(3^{3k})}$	${\displaystyle O(n^{2})}$	โรเบิร์ตสันและเซย์มัวร์ (1995)
${\displaystyle 8k+7}$	${\displaystyle 2^{O(k\log n)}}$	${\displaystyle O(n\log ^{2}n)}$	ลาเกอร์เกรน (1996)
${\displaystyle 5k+4}$(หรือ)${\displaystyle 7k+6}$	${\displaystyle 2^{O(k\log n)}}$	${\displaystyle O(n\log n)}$	รีด (1992)
ที่แน่นอน	${\displaystyle 2^{O(k^{3})}}$	${\displaystyle O(n)}$	บอดแลนเดอร์ (1996)
${\displaystyle O\left(k\cdot {\sqrt {\log k}}\right)}$	${\displaystyle 1}$	${\displaystyle n^{O(1)}}$	ไฟกี, ฮาเจียกายี และลี (2008)
${\displaystyle 4.5k+4}$	${\displaystyle 2^{3k}}$	${\displaystyle O(n^{2})}$	อามีร์ (2010)
${\displaystyle {\tfrac {11}{3}}k+4}$	${\displaystyle 2^{3.6982k}}$	${\displaystyle O(n^{3}\log ^{4}n)}$	อามีร์ (2010)
ที่แน่นอน	${\displaystyle 1}$	${\displaystyle O(1.7347^{n})}$	โฟมิน, โทดินกา และวิลเลจเจอร์ (2015)
${\displaystyle 3k+2}$	${\displaystyle 2^{O(k)}}$	${\displaystyle O(n\log n)}$	บอดแลนเดอร์และคณะ (2016)
${\displaystyle 5k+4}$	${\displaystyle 2^{O(k)}}$	${\displaystyle O(n)}$	บอดแลนเดอร์และคณะ (2016)
${\displaystyle k^{2}}$	${\displaystyle k^{7}}$	${\displaystyle O(n\log n)}$	โฟมินและคณะ (2018)
${\displaystyle 5k+4}$	${\displaystyle 2^{8.765k}}$	${\displaystyle O(n\log n)}$	เบลบาซีและฟือเรอร์ (2021a)
${\displaystyle 2k+1}$	${\displaystyle 2^{O(k)}}$	${\displaystyle O(n)}$	คอร์โฮเนน (2021)
${\displaystyle 5k+4}$	${\displaystyle 2^{6.755k}}$	${\displaystyle O(n\log n)}$	เบลบาซีและฟือเรอร์ (2021b)
ที่แน่นอน	${\displaystyle 2^{O(k^{2})}}$	${\displaystyle O(n^{4})}$	คอร์โฮเนนและล็อกชทานอฟ (2023)
${\displaystyle (1+\varepsilon )k}$	${\displaystyle k^{O(k/\varepsilon )}}$	${\displaystyle O(n^{4})}$	คอร์โฮเนนและล็อกชทานอฟ (2023)

ไม่ทราบว่าการกำหนด treewidth ของกราฟระนาบเป็นปัญหา NP-complete หรือไม่ หรือว่า treewidth ของกราฟระนาบสามารถคำนวณได้ในเวลาพหุนามหรือ ไม่ ^{[ 13 ]}

ในทางปฏิบัติ อัลกอริทึมของShoikhet & Geiger (1997)สามารถกำหนด treewidth ของกราฟที่มีจุดยอดได้ถึง 100 จุด และ treewidth ได้ถึง 11 โดยการค้นหาการเติมเต็มแบบคอร์ดัลของกราฟเหล่านี้ด้วย treewidth ที่เหมาะสมที่สุด

สำหรับกราฟขนาดใหญ่ สามารถใช้เทคนิคการค้นหา เช่นการค้นหาแบบแยกสาขาและขอบเขตเพื่อคำนวณความกว้างของต้นไม้ อัลกอริทึมเหล่านี้สามารถทำงานได้ทุกเมื่อกล่าวคือ เมื่อหยุดก่อนกำหนด จะให้ค่าขอบเขตบนของความกว้างของต้นไม้ อัลกอริทึมประเภทนี้ได้รับการเสนอในปี 2547 โดย Vibhav Gogate และRina Dechterเพื่อให้ได้ค่าขอบเขตล่างของความกว้างของต้นไม้สำหรับสาขาของการค้นหานี้ พวกเขาสร้างกราฟไมเนอร์โดยการยุบขอบระหว่างจุดยอดที่มีดีกรีต่ำสุดกับจุดยอดข้างเคียงซ้ำๆ จนกว่าจะเหลือเพียงจุดยอดเดียว ค่าสูงสุดของดีกรีต่ำสุดในไมเนอร์ที่สร้างขึ้นเหล่านี้รับประกันได้ว่าเป็นค่าขอบเขตล่างของความกว้างของต้นไม้ของกราฟ^{[ 14 ]} Alex Dow และ Rich Korf ได้ปรับปรุงอัลกอริทึมนี้เพิ่มเติมโดยใช้ การค้นหา แบบbest-first ^{[ 15 ]}

ในช่วงต้นทศวรรษ 1970 มีการสังเกตว่า ปัญหา การเพิ่มประสิทธิภาพเชิงการจัดเรียง จำนวนมาก ที่กำหนดบนกราฟสามารถแก้ไขได้อย่างมีประสิทธิภาพโดย การเขียน โปรแกรมแบบไดนามิก ที่ไม่ใช่แบบอนุกรม ตราบใดที่กราฟมีมิติ ที่จำกัด ^{[ 16 ]}ซึ่งเป็นพารามิเตอร์ที่Bodlaender (1998) แสดงให้เห็นว่าเทียบเท่ากับ treewidth ต่อมาในช่วงปลายทศวรรษ 1980 ผู้เขียนหลายคนได้สังเกตอย่างอิสระ^{[ 17 ]}ว่าปัญหาเชิงอัลกอริทึมจำนวนมากที่เป็นNP-completeสำหรับกราฟใดๆ อาจแก้ไขได้อย่างมีประสิทธิภาพโดยการเขียนโปรแกรมแบบไดนามิกสำหรับกราฟที่มี treewidth ที่จำกัด โดยใช้การแบ่งส่วนต้นไม้ของกราฟเหล่านี้

ตัวอย่างเช่น ปัญหาการระบายสีกราฟที่มีความกว้างของต้นไม้เท่ากับ n อาจแก้ไขได้โดยใช้ อัลกอริธึม การเขียนโปรแกรมเชิงพลวัตบนโครงสร้างต้นไม้ของกราฟ สำหรับแต่ละกลุ่มของโครงสร้างต้นไม้ และแต่ละการแบ่งจุดยอดออกเป็นกลุ่มสี อัลกอริธึมจะพิจารณาว่าการระบายสีนั้นถูกต้องและสามารถขยายไปยังโหนดลูกหลานทั้งหมดในโครงสร้างต้นไม้ได้หรือไม่ โดยการรวมข้อมูลประเภทเดียวกันที่คำนวณและจัดเก็บไว้ที่โหนดเหล่านั้น อัลกอริธึมที่ได้จะค้นหาการระบายสีที่เหมาะสมที่สุดของกราฟที่มีจุดยอด n ในเวลาซึ่งเป็นขอบเขตเวลาที่ทำให้ปัญหานี้สามารถแก้ไขได้ด้วยพารามิเตอร์คงที่ ${\displaystyle k}$${\displaystyle X_{i}}$${\displaystyle X_{i}}$${\displaystyle n}$${\displaystyle O(k^{k+O(1)}n)}$

สำหรับปัญหากลุ่มใหญ่ มีอัลกอริทึมเวลาเชิงเส้นในการแก้ปัญหาจากกลุ่มนั้น หากมีการแบ่งต้นไม้ ที่มีความกว้างของต้นไม้คงที่และมีขอบเขต โดยเฉพาะอย่างยิ่ง ทฤษฎีบทของ Courcelle ^{[ 18 ]}ระบุว่า หากปัญหาเกี่ยวกับกราฟสามารถแสดงในตรรกะของกราฟโดยใช้ตรรกะลำดับที่สองแบบเอกภาคได้ ปัญหา นั้นก็จะสามารถแก้ไขได้ในเวลาเชิงเส้นบนกราฟที่มีความกว้างของต้นไม้ที่มีขอบเขต ตรรกะลำดับที่สองแบบเอกภาคเป็นภาษาที่ใช้อธิบายคุณสมบัติของกราฟโดยใช้โครงสร้างต่อไปนี้:

• การดำเนินการทางตรรกะ เช่น${\displaystyle \wedge ,\vee ,\neg ,\Rightarrow }$
• การทดสอบการเป็นสมาชิก เช่น,${\displaystyle e\in E}$${\displaystyle v\in V}$
• การกำหนดปริมาณเหนือจุดยอด ขอบ เซตของจุดยอด และ/หรือเซตของขอบ เช่น, , ,${\displaystyle \forall v\in V}$${\displaystyle \exists e\in E}$${\displaystyle \exists I\subset V}$${\displaystyle \forall F\subset E}$
• การทดสอบความสัมพันธ์ระหว่างจุดยอดและขอบ ( ซึ่งเป็นจุดสิ้นสุดของการทดสอบ) และส่วนขยายบางอย่างที่ช่วยให้สามารถทำสิ่งต่างๆ เช่น การเพิ่มประสิทธิภาพได้${\displaystyle u}$${\displaystyle e}$

ยกตัวอย่างเช่นปัญหาการระบายสี 3 สีสำหรับกราฟ สำหรับกราฟปัญหานี้ถามว่า เป็นไปได้หรือไม่ที่จะกำหนดสีให้กับแต่ละจุดยอดหนึ่งในสามสี โดยที่ไม่มีจุดยอดที่อยู่ติดกันสองจุดใดได้รับสีเดียวกัน ปัญหานี้สามารถแสดงในตรรกะลำดับที่สองแบบเอกภาคได้ดังนี้ โดย ที่, , แทนเซตย่อยของจุดยอดที่มีแต่ละสีทั้งสามสี และโดยที่นิพจน์ย่อยถูกกำหนดให้หมายถึง (ไม่จำเป็นต้องรวมข้อกำหนดที่ว่าเซตต้องไม่ซ้อนทับกันในสูตรนี้) ดังนั้น จากผลลัพธ์ของ Courcelle ปัญหาการระบายสี 3 สีสามารถแก้ไขได้ในเวลาเชิงเส้นสำหรับกราฟที่กำหนดโดยการแยกส่วนต้นไม้ที่มีความกว้างของต้นไม้คงที่และมีขอบเขต ${\displaystyle G=(V,E)}$${\displaystyle v\in V}$$${\displaystyle \exists W_{1}\subseteq V\ \exists W_{2}\subseteq V\ \exists W_{3}\subseteq V\ \left({\begin{aligned}&\forall v\in V\ (v\in W_{1}\vee v\in W_{2}\vee v\in W_{3})\wedge {}\\&\operatorname {independent} (W_{1})\wedge {}\\&\operatorname {independent} (W_{2})\wedge {}\\&\operatorname {independent} (W_{3})\\\end{aligned}}\right),}$$${\displaystyle W_{1}}$${\displaystyle W_{2}}$${\displaystyle W_{3}}$${\displaystyle \operatorname {independent} (W_{i})}$$${\displaystyle \operatorname {independent} (W_{i})\equiv \forall e\in E\ \exists v\in V\ (\operatorname {endpoint} (v,e)\wedge \neg v\in W_{i}).}$$${\displaystyle W_{i}}$

ความกว้างของเส้นทางของกราฟมีคำจำกัดความที่คล้ายคลึงกับความกว้างของต้นไม้ผ่านการแยกส่วนต้นไม้ แต่ถูกจำกัดไว้เฉพาะการแยกส่วนต้นไม้ซึ่งต้นไม้พื้นฐานของการแยกส่วนเป็นกราฟเส้นทาง หรืออีกทางหนึ่ง ความกว้างของเส้นทางอาจถูกกำหนดจากกราฟช่วงเวลาในลักษณะเดียวกับคำจำกัดความของความกว้างของต้นไม้จากกราฟคอร์ดัล ผลที่ตามมาคือ ความกว้างของเส้นทางของกราฟจะมีขนาดอย่างน้อยเท่ากับความกว้างของต้นไม้เสมอ แต่จะมีขนาดใหญ่กว่าได้เพียงปัจจัยลอการิทึมเท่านั้น^{[ 5 ]}พารามิเตอร์อีกตัวหนึ่งคือแบนด์วิดท์ของกราฟมีคำจำกัดความที่คล้ายคลึงกันจากกราฟช่วงเวลาที่เหมาะสมและมีขนาดอย่างน้อยเท่ากับความกว้างของเส้นทาง พารามิเตอร์อื่นๆ ที่เกี่ยวข้อง ได้แก่ความลึกของต้นไม้ซึ่งเป็นจำนวนที่มีขอบเขตสำหรับตระกูลกราฟปิดไมเนอร์ก็ต่อเมื่อตระกูลนั้นไม่รวมเส้นทาง และความเสื่อมซึ่งเป็นการวัดความเบาบางของกราฟที่มีค่าอย่างมากที่สุดเท่ากับความกว้างของต้นไม้

เนื่องจาก treewidth ของกราฟกริดคือtreewidth ของกราฟจึงมากกว่าหรือเท่ากับขนาดของไมเนอร์กริดสี่เหลี่ยมที่ใหญ่ที่สุดของในทางกลับกันทฤษฎีบทไมเนอร์กริดโดยRobertsonและSeymourแสดงให้เห็นว่ามีฟังก์ชันที่ไม่จำกัดอยู่เช่นนั้น ไมเนอร์กริดสี่เหลี่ยมที่ใหญ่ที่สุดของกราฟที่มี treewidth มีขนาดอย่างน้อย[ ^{19 ] ขอบเขต}ที่ดีที่สุดที่ทราบเกี่ยวกับคือต้องมีอย่างน้อยสำหรับค่าคงที่ บางค่าและอย่างมาก^{[ 20 ]}${\displaystyle n\times n}$${\displaystyle n}$${\displaystyle G}$${\displaystyle G}$${\displaystyle f}$${\displaystyle k}$${\displaystyle f(k)}$${\displaystyle f}$${\displaystyle f}$${\displaystyle \Omega (k^{d})}$${\displaystyle d>0}$$${\displaystyle O\left({\sqrt {r/\log r}}\right).}$$

(สำหรับสัญลักษณ์ในขอบเขตล่าง โปรดดูสัญลักษณ์บิ๊กโอ ) ขอบเขตที่แน่นกว่าเป็นที่รู้จักสำหรับตระกูลกราฟที่จำกัด ซึ่งนำไปสู่อัลกอริทึมที่มีประสิทธิภาพสำหรับปัญหาการเพิ่มประสิทธิภาพกราฟจำนวนมากในตระกูลเหล่านั้นผ่านทฤษฎีมิติคู่ [ ^{21 ] ทฤษฎีบท}กริดของ Halinให้ความสัมพันธ์แบบอนาล็อกระหว่างความกว้างของต้นไม้และขนาดไมเนอร์กริดสำหรับกราฟอนันต์^{[ 22 ]}${\displaystyle \Omega }$

กล่าวกันว่าตระกูล ของกราฟที่ปิดภายใต้การรับซับกราฟนั้นมี treewidth เฉพาะที่จำกัดหรือคุณสมบัติ treewidth ตามเส้นผ่านศูนย์กลางหาก treewidth ของกราฟในตระกูลนั้นมีขอบเขตบนโดยฟังก์ชันของเส้นผ่านศูนย์กลางหากถือว่าคลาสนั้นปิดภายใต้การรับไมเนอร์ ด้วย แล้วจะมี treewidth เฉพาะที่จำกัดก็ต่อเมื่อไมเนอร์ต้องห้ามตัว ใดตัวหนึ่ง เป็นกราฟยอด [ ^{23 ] การ}พิสูจน์ดั้งเดิมของผลลัพธ์นี้แสดงให้เห็นว่า treewidth ในตระกูลกราฟที่ไม่มีไมเนอร์ยอดจะเติบโตอย่างมากที่สุดแบบเลขชี้กำลังสองเท่าตามฟังก์ชันของเส้นผ่านศูนย์กลาง^{[ 24 ]}ต่อมาสิ่งนี้ลดลงเหลือเลขชี้กำลังเดียว^{[ 21 ]}และในที่สุดก็เหลือขอบเขตเชิงเส้น^{[ 25 ]} ความกว้างของต้นไม้ท้องถิ่นที่จำกัดมีความเกี่ยวข้องอย่างใกล้ชิดกับทฤษฎีอัลกอริทึมของมิติสองมิติ [ ^{26 ] และคุณสมบัติของกราฟทุกอย่างที่กำหนดได้ในตรรกะลำดับแรกสามารถตัดสินได้สำหรับตระกูลกราฟ ที่}ไม่มีเอเพ็กซ์ไมเนอร์ในปริมาณเวลาที่มากกว่าเชิงเส้นเล็กน้อย^{[ 27 ]}${\displaystyle F}$${\displaystyle F}$${\displaystyle F}$

นอกจากนี้ ยังเป็นไปได้ที่กราฟคลาสที่ไม่ปิดภายใต้ไมเนอร์จะมี treewidth เฉพาะที่จำกัด โดยเฉพาะอย่างยิ่ง สิ่งนี้เป็นจริงอย่างเห็นได้ชัดสำหรับกราฟคลาสที่มีดีกรีจำกัด เนื่องจากกราฟย่อยที่มีเส้นผ่านศูนย์กลางจำกัดจะมีขนาดจำกัด ตัวอย่างอื่น ๆ ได้แก่กราฟระนาบ 1ซึ่งเป็นกราฟที่สามารถวาดลงบนระนาบได้โดยมีจุดตัดหนึ่งจุดต่อขอบ และโดยทั่วไปสำหรับกราฟที่สามารถวาดลงบนพื้นผิวที่มีจีนัสจำกัดโดยมีจำนวนจุดตัดต่อขอบที่จำกัด เช่นเดียวกับตระกูลกราฟที่ปิดไมเนอร์ซึ่งมี treewidth เฉพาะที่จำกัด คุณสมบัตินี้ได้ชี้ทางไปสู่ขั้นตอนวิธีประมาณค่าที่มีประสิทธิภาพสำหรับกราฟเหล่านี้^{[ 28 ]}

Halin (1976)ได้นิยามกลุ่มของพารามิเตอร์กราฟที่เขาเรียกว่า ฟังก์ชัน Sซึ่งรวมถึง treewidth ด้วย ฟังก์ชันเหล่านี้แปลงกราฟเป็นจำนวนเต็มและต้องมีค่าเป็นศูนย์ในกราฟที่ไม่มีขอบต้องเป็น ฟังก์ชัน minor-monotone (ฟังก์ชันจะถูกเรียกว่า "minor-monotone" ถ้าเมื่อใดก็ตามที่เป็น minor ของจะได้) ต้องเพิ่มขึ้นหนึ่งเมื่อมีการเพิ่มจุดยอดใหม่ที่อยู่ติดกับจุดยอดก่อนหน้าทั้งหมดและต้องเลือกค่าที่มากกว่าจากกราฟย่อยสองกราฟที่อยู่ด้านใดด้านหนึ่งของตัวคั่นคลิก เซต ของฟังก์ชันดังกล่าวทั้งหมดจะประกอบกันเป็นแลตทิซที่สมบูรณ์ภายใต้การดำเนินการหาค่าต่ำสุดและสูงสุดแบบทีละองค์ประกอบ องค์ประกอบบนสุดในแลตทิซนี้คือ treewidth และองค์ประกอบล่างสุดคือจำนวน Hadwigerซึ่งเป็นขนาดของminor ที่สมบูรณ์ ที่ใหญ่ที่สุด ในกราฟที่กำหนด ${\displaystyle f}$${\displaystyle H}$${\displaystyle G}$${\displaystyle f(H)\leq f(G)}$