Parameters Tied to Treewidth

2016/03/31 by Daniel J. Harvey, David R. Wood · 9 citations

paper · doi:10.1002/jgt.22030

Abstract

Abstract Treewidth is a graph parameter of fundamental importance to algorithmic and structural graph theory. This article surveys several graph parameters tied to treewidth, including separation number, tangle number, well‐linked number, and Cartesian tree product number. We review many results in the literature showing these parameters are tied to treewidth. In a number of cases we also improve known bounds, provide simpler proofs, and show that the inequalities presented are tight.

Cited by

• Induced minors and subpolynomial treewidth
• Optimal Tree-Decompositions with Bags of Bounded Treewidth
• String Graphs: Product Structure and Localised Representations
• Optimal tree-decompositions with bags of bounded pathwidth
• Tree-independence number VI. Thetas and pyramids
• Expansion of gap-planar graphs
• Tree decompositions with small width, spread, order and degree
• Embedding Graphs of Simple Treewidth into Sparse Products
• On universal graphs for trees and treewidth k graphs

Related

• Parameters Tied to Treewidth
• Separation Number and Treewidth, Revisited
• The Treewidth of Line Graphs
• Edge-trewidth: Algorithmic and combinatorial properties
• Large-Treewidth Graph Decompositions and Applications