On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree

Abstract

The band-, tree-, and clique-width are of primary importance in algorithmic graph theory due to the fact that many problems that are NP-hard for general graphs can be solved in polynomial time when restricted to graphs where one of these parameters is bounded. It is known that for any fixed $\Delta \geq 3$, all three parameters are unbounded for graphs with vertex degree at most $Delta$. In this paper, we distinguish representative subclasses of graphs with bounded vertex degree that have bounded band-, tree-, or clique-width. Our proofs are constructive and lead to efficient algorithms for a variety of NP-hard graph problems when restricted to those classes.