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

  • 2
    $\begingroup$ Sorry, I stumbled on the paper A tourist guide through treewidth again. This is worth cosidering I guess. $\endgroup$ Jul 24, 2019 at 6:12
  • 1
    $\begingroup$ I highly recommend Bruce Reed's chapter on treewidth in a book. See link below. cambridge.org/core/books/surveys-in-combinatorics-1997/… $\endgroup$ Jul 24, 2019 at 19:50
  • 1
    $\begingroup$ Martin Grohe's article on tangles is another related article though I have not yet read it yet. Tangles and Connectivity in Graphs. arxiv.org/abs/1602.04727 $\endgroup$ Jul 24, 2019 at 20:02
  • $\begingroup$ Another candidate: Treewidth: Characterizations, Applications, and Computations by Bodlaender $\endgroup$ Jul 25, 2019 at 4:34
  • $\begingroup$ Yet another: Tree Decompositions, Treewidth, and NP-Hard Problems, by Voigt $\endgroup$ Jul 25, 2019 at 6:46


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.