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$ – Cyriac Antony Jul 24 '19 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$ – Chandra Chekuri Jul 24 '19 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$ – Chandra Chekuri Jul 24 '19 at 20:02
  • $\begingroup$ Another candidate: Treewidth: Characterizations, Applications, and Computations by Bodlaender $\endgroup$ – Cyriac Antony Jul 25 '19 at 4:34
  • $\begingroup$ Yet another: Tree Decompositions, Treewidth, and NP-Hard Problems, by Voigt $\endgroup$ – Cyriac Antony Jul 25 '19 at 6:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.