Treewidth Of Graphs And Chordal Completion

236 Views Asked by At

https://en.wikipedia.org/wiki/Treewidth

The above page explains what a tree decomposition is, and states that treewidth of G is equal to the minimum clique number, minus one, of a chordal supergraph of G.

Where can I find a proof of this and basic facts about treewidth, and just generally an introduction to this concept of treewidth, in accessible form?

1

There are 1 best solutions below

0
On

I am mostly familiar with (bounded) treewidth in relation to optimization and approximation algorithms on graphs. Many optimization problems are easy (easier) on trees and solutions for more general graphs can be "built up" from a good tree decomposition.

There are a few survey papers/tutorials online. One such tutorial is "Combinatorial Optimization on Graphs of Bounded Treewidth" by Bodlaender and Koster.