An introduction to treewidth
Daniela Bronner, Bernard Ries · Infoscience (Ecole Polytechnique Fédérale de Lausanne) · 2006
The notion of treewidth has seen to be a powerful vehicle for many graph algorithmic studies. A lot of problems, which are in general $NP$-complete, can be solved in polynomial time for graphs with small treewidth. In the first part of this paper we present three different definitions of treewidth and we show their equivalence. The second part consists of an overview of the complexity status of the treewidth problem as well as of algorithmics results. We also discuss a polynomial time algorithm for computing the treewidth of circle graphs.