5
$\begingroup$

Can someone recommend a graph theory textbook that covers treewidth thoroughly?

Something that focuses on the graph-theoretic structure of bounded treewidth graphs rather than solving problems on them. Don't need the strongest/newest results but would prefer something that

Preferably something that covers sublinear treewidth of planar and minor free graphs.

$\endgroup$

1 Answer 1

1
$\begingroup$

I don't know if the thing you are looking for exists, but here are at least some pointers:

Parameterized Algorithms by Cygan et al (free PDF version) has a chapter dedicated on the topic. This is slightly algorithms oriented, but contains structural stuff too.

Graph Theory by Diestel has one chapter, (12. Minors, Trees and WQO) on the subject, about 40 pages. homepage

Bodlaender has a chapter Treewidth of Graphs in the Encyclopedia of Algorithms. homepage

Heggernes has a short compendium used for her advanced algorithms class Treewidth, partial $k$-trees, and chordal graphs.

You also have Ton Kloks' book, Treewidth springer, but it's getting rather old. I have not read this one, so I don't know much about it.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.