zbMATH — the first resource for mathematics

Some classes of graphs with bounded treewidth. (English) Zbl 0684.68047
The notion of treewidth of a graph was introduced by N. Robertson and P. Seymour [J. Algorithms 7, 309-322 (1986; Zbl 0611.05017)]. For classes of planar graphs (k-outerplanar graphs, graphs with radius k) upper bounds are proved on the treewidth of these graphs. This research is motivated by the fact that many NP-hard graph problems are polynomially solvable when restricted to graphs with bounded treewidth.
Reviewer: R.Klette

68Q25 Analysis of algorithms and problem complexity
05C38 Paths and cycles
68R10 Graph theory (including graph drawing) in computer science