CoordenaÃÃo de AperfeÃoamento de Pessoal de NÃvel Superior / The concept of treewidth was introduced by Robertson and Seymour. Treewidth may be defined as the size of the largest vertex set in a tree decomposition. Recent results show that several NP-Complete problems can be solved in polynomial time, or linear, when restricted to graphs with small treewidth. In our bibliographic research, we focus attention on the calculation of lower bounds for the treewidth and we described, in our dissertation, some of the principal results already available in the literature. We realize that linear-integer formulations for determining the treewidth are very limited in the literature and there are no studies available on the polyhedra associated with them. The Elimination Order Formulation (EOF) has been proposed by Koster and Bodlaender. It is based on orderly disposal of vertices and the relationship between the treewidth of a graph and its chordalizations. As a result of our study, we present a simplification of EOF formulation, we show that the polyhedron associated with this simplification is affine isomorphic to the EOF formulation. We determine the dimension of the polyhedron associated with the simplification, we briefly present a set of very simple facets and we introduce, analyse and demonstrate be a facet, some more complex inequalities. / O conceito de largura em Ãrvore (âtreewidthâ) foi introduzido por Robertson e Seymour. A largura em Ãrvore de um grafo G à o mÃnimo k tal que G pode ser decomposto em uma DecomposiÃÃo em Ãrvore (DEA) com cada subconjunto de vÃrtice com no mÃximo k+1 vÃrtices. Resultados recentes demonstram que vÃrios problemas NP-Completos podem ser resolvidos em tempo polinomial, ou ainda linear, quando restritos a grafos com largura em Ãrvore pequena. Em nossa pesquisa bibliogrÃfica, focamos a atenÃÃo no cÃlculo de limites inferiores para a largura em Ãrvore e descrevemos, em nossa dissertaÃÃo, alguns dos resultados jà disponÃveis na literatura. NÃs percebemos que formulaÃÃes lineares-inteiras para a determinaÃÃo da largura em Ãrvore sÃo limitadas na literatura e nÃo hà estudos disponÃveis sobre os poliedros associados a elas. A formulaÃÃo por ordem de eliminaÃÃo (EOF) foi proposta por Koster e Bodlaender. Ela à baseada na eliminaÃÃo ordenada de vÃrtices e na relaÃÃo entre a largura em Ãrvore de um grafo e suas cordalizaÃÃes. Como resultado de nosso estudo, apresentamos uma simplificaÃÃo da formulaÃÃo EOF, demonstramos que o poliedro associado a simplificaÃÃo à afim-isomÃrfico ao da formulaÃÃo EOF, verificamos a dimensÃo do poliedro associado à simplificaÃÃo, apresentamos brevemente um rol de facetas muito simples desse poliedro e, em seguinte, introduzimos, analisamos e demonstramos ser faceta algumas desigualdades mais complexas.

CoordenaÃÃo de AperfeiÃoamento de Pessoal de NÃvel Superior / Os conceitos de DecomposiÃÃo em Ãrvore e Largura em Ãrvore foram introduzidos por Robertson e Seymour em sua sÃrie de artigos sobre menores de grafos, publicados ao longo da dÃcada de 90. Sabe-se que muitos problemas NP - difÃceis podem ser resolvidos polinomialmente para um grafo G, dada uma decomposiÃÃo em Ãrvore de G de largura limitada. Logo, limitar a largura em Ãrvore de uma classe de grafos torna-se um objeto de estudo de grande interesse. Neste contexto, a classe dos grafos planares se mostra bastante intrigante, uma vez que, apesar de possuir outras mÃtricas limitadas em valores baixos (por exemplo, nÃmero cromÃtico), nÃo possui largura em Ãrvore limitada. Desta forma, uma alternativa à restringir a classe estudada para uma subclasse dos grafos planares. Neste trabalho, nÃs investigamos a classe dos grafos planares livres de buracos pares. NÃs mostramos que se G à um grafo planar livre de buracos pares, entÃo ele nÃo contÃm uma subdivisÃo de uma grade 10  10. Portanto, se os menores grades de G sÃo obtidos de subdivisÃes G tem largura em Ãrvore no mÃximo 49. AlÃm disso, dois algoritmos nÃo exatos polinomiais para computar uma decomposiÃÃo em Ãrvore de um grafo planar livre de buracos pares sÃo apresentados, ambos baseados em caracterizaÃÃes conhecidas de tal classe de grafos. No primeiro algoritmo, uma decomposiÃÃo em Ãrvore à construÃda a partir de grafos bÃsicos pela concatenaÃÃo de decomposiÃÃes em Ãrvores de pedaÃos pequenos via os cortes clique, k-estrelas (k = 1; 2; 3) e 2-join. No segundo, uma decomposiÃÃo em Ãrvore à construÃda pela inclusÃo dos vÃrtices de G um a um, seguindo sua ordem bi-simplicial. / 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.