Clique-width and tree-width of sparse graphs
Bruno Courcelle · 2015
Tree-width and clique-width are two important graph complexity measures that serve as parameters in many xed-parameter tractable (FPT) algorithms. The same classes of sparse graphs, in particular of planar graphs and of graphs of bounded degree have bounded tree-width and bounded clique-width. We prove that, for sparse graphs, clique-width is polynomially bounded in terms of tree-width. For planar and incidence graphs, we establish linear bounds. Our motivation is the construction of FPT algorithms based on automata that take as input the algebraic terms denoting graphs of bounded clique-width. These algorithms can check properties of graphs of bounded tree-width expressed by monadic secondorder formulas written with edge set quantications. We give an algorithm that transforms tree-decompositions into clique-width terms that match the proved upper-bounds. keywords: tree-width; clique-width; graph decomposition; sparse graph; incidence graph