---
abstract: 'Treewidth is a graph parameter of fundamental importance to algorithmic and structural graph theory. This paper describes several graph parameters tied to treewidth, including separation number, tangle number, well-linked number and cartesian tree product number. We prove that 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.'
address:
- 'Department of Mathematics and Statistics The University of Melbourne Melbourne, Australia'
- 'School of Mathematical Sciences Monash University Melbourne, Australia'
author:
- 'Daniel J. Harvey'
- 'David R. Wood'
bibliography:
- 'myBibliography.bib'
- 'extra.bib'
title: Parameters Tied to Treewidth
---

[^1] [^2]

Introduction
============

Treewidth is an important graph parameter for two key reasons. Firstly, treewidth has many algorithmic applications; for example, there are many results showing that NP-Hard problems can be solved in polynomial time on classes of graphs with bounded treewidth (see @Bodlaender-AC93 for a survey). Treewidth is inherently related to graph separators, which are “small" sets of vertices whose removal leaves no component with more than half the vertices (or thereabouts). Separators are particularly useful when using dynamic programming to solve graph problems; find and delete a separator, 