An introduction to treewidth

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.