<p>I am searching for a good book (or survey paper) on treewidth. I would be delighted if the book/paper surveys multiple approaches to treewidth (eg: structural, algorithmic, `language-theoretic') and also discusses on treewidth in isolation.</p>

<p>The book I found is <em>Treewidth: Computations and Approximations</em>, by Ton Kloks. This book approaches treewidth from a structural point of view (partial <span class="math-container">$k$</span>-tree, chordal completion) and also algorithmic point of view. It covers treewidth computation and approximation in special graph classes, and talks about treewidth bounded graphs.</p>

<p><em>Is this book a must-read?</em> Or is there any other choice out there?</p>

<p>I liked the game theoretic definition of treewidth in the survey <em>Practical algorithms for MSO model-checking on tree-decomposable graphs</em>, Langer et. al. It is equivalent to the traditional tree-decomposition based definition in a natural way (As a sidenote, now there is a game theoretic approach to MSO model checking).</p>

<p><strong>Could you point out a book/paper on treewidth that keeps multiple appraches to it in mind?</strong></p>

<p>Thank you</p>

CC BY-SA 4.0
2019-07-24T06:12:20.993Z
Sorry, I stumbled on the paper *A tourist guide through treewidth* again. This is worth cosidering I guess.
Cyriac Antony
CC BY-SA 4.0
2019-07-24T19:50:35.087Z
I highly recommend Bruce Reed's chapter on treewidth in a book. See link below.
 
https://www.cambridge.org/core/books/surveys-in-combinatorics-1997/tree-width-and-tangles-a-new-connectivity-measure-and-some-applications/50B61BC367CC21EA85F02038F3CC632D
Chandra Chekuri
CC BY-SA 4.0
2019-07-24T20:02:01.117Z
Martin Grohe's article on tangles is another related article though I have not yet read it yet. Tangles and Connectivity in Graphs. https://arxiv.org/abs/1602.04727
Chandra Chekuri
CC BY-SA 4.0
2019-07-25T04:34:36.910Z
Another candidate: *Treewidth: Characterizations, Applications, and Computations* by Bodlaender
Cyriac Antony
CC BY-SA 4.0
2019-07-25T06:46:00.897Z
Yet another: *Tree Decompositions, Treewidth, and NP-Hard Problems*, by Voigt
Cyriac Antony
<reference-request><soft-question>
Book recommendation treewidth
Cyriac Antony
# Book recommendation treewidth

(Asked by: username_0 on 2019-07-24)

I am searching for a good book (or survey paper) on treewidth. I would be delighted if the book/paper surveys multiple approaches to treewidth (eg: structural, algorithmic, `language-theoretic') and also discusses on treewidth in isolation.

The book I found is *Treewidth: Computations and Approximations*, by Ton Kloks. This book approaches treewidth from a structural point of view (partial $k$-tree, chordal completion) and also algorithmic point of view. It covers treewidth computation and approximation in special graph classes, and talks about treewidth bounded graphs.

*Is this book a must-read?* Or is there any other choice out there?

I liked the game theoretic definition of treewidth in the survey *Practical algorithms for MSO model-checking on tree-decomposable graphs*, Langer et. al. It is equivalent to the traditional tree-decomposition based definition in a natural way (As a sidenote, now there is a game theoretic approach to MSO model checking).

**Could you point out a book/paper on treewidth that keeps multiple appraches to it in mind?**

Thank you

**Tags:** reference-request, soft-question
> **Comments:**
> **username_0**: Sorry, I stumbled on the paper *A tourist guide through treewidth* again. This is worth cosidering I guess.  
> **username_1**: I highly recommend Bruce Reed's chapter on treewidth in a book. See link below.   https://www.cambridge.org/core/books/surveys-in-combinatorics-1997/tree-width-and-tangles-a-new-connectivity-measure-and-some-applications/50B61BC367CC21EA85F02038F3CC632D  
> **username_1**: Martin Grohe's article on tangles is another related article though I have not yet read it yet. Tangles and Connectivity in Graphs. https://arxiv.org/abs/1602.04727  
> **username_0**: Another candidate: *Treewidth: Characterizations, Applications, and Computations* by Bodlaender  
> **username_0**: Yet another: *Tree Decompositions, Treewidth, and NP-Hard Problems*, by Voigt  

---

## 0 answers

