Decomposição e largura em árvore de grafos planares livres de ciclos pares induzidos

Abstract

The definitions of tree decomposition and treewidth were introduced by Robertson and Seymour in their series of papers on graph minors, published during the nineties. It is known that many NP-hard problems can be polynomially solved if a tree decomposition of bounded treewidth is given. So, it is of interest to bound the treewidth of certain classes of graphs. In this context, the planar graphs seem to be specially challenging because, in despite of having many known bounded metrics (for example, chromatic number), they have unbounded treewidth. So, an alternative approach is to restrict ourselves to a subclass of planar graphs. In this work, we investigate the class of even-hole-free planar graphs. We show that if G is an even-hole-free planar graph, then it does not contain a subdivision of the 10£10 grid. So, if the grid minors of G are obtained from subdivisions, then G has treewidth at most 49. Furthermore, two polynomial, non-exact algorithms to compute a tree decomposition of a even-hole-free planar graph are given, both based on known characterizations of even-hole-free graphs. In the ¯rst one, a tree decomposition is built from basic graphs by concatenating the tree decomposition of small pieces via the clique, k-stars (k = 1; 2; 3) and 2-join cutsets. In the second one, a tree decomposition is built by including one by one the vertices of G, following their bi-simplicial order.