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.
| Identifer | oai:union.ndltd.org:IBICT/oai:www.teses.ufc.br:1174 |
| Date | 27 August 2007 |
| Creators | Aline Alves da Silva |
| Contributors | ClÃudia Linhares Sales, Ricardo Cordeiro CorrÃa, Sulamita Klein |
| Publisher | Universidade Federal do CearÃ, Programa de PÃs-GraduaÃÃo em CiÃncia da ComputaÃÃo, UFC, BR |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFC, instname:Universidade Federal do Ceará, instacron:UFC |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0106 seconds