Parameters Tied to Treewidth

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.

22 pages, 1 figure

References in corpus (2)

• Polynomial treewidth forces a large grid-like-minor
• Constructing dense graphs with sublinear Hadwiger number