Parameters Tied to Treewidth

2013/12/12 by Harvey, Daniel J., Wood, David R. · 9 citations
#05C75 (Primary) 05C72 #05C76 #05C83 (Secondary) #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1312.3401

Abstract

Treewidth is a graph parameter of fundamental importance to algorithmic and structural graph theory. This paper 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
• Large-Treewidth Graph Decompositions and Applications
• Edge-trewidth: Algorithmic and combinatorial properties