Menores de grafos: largura em árvores de grafos planares
Carregando...
Data
Autor(es)
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Minas Gerais
Descrição
Tipo
Dissertação de mestrado
Título alternativo
Graph minors: width in planar graph trees
Primeiro orientador
Membros da banca
Csaba Schneider
Danielle Franco Nicolau
Deisiane Lopes Gonçalves
Sérgio Henrique Nogueira
Danielle Franco Nicolau
Deisiane Lopes Gonçalves
Sérgio Henrique Nogueira
Resumo
A teoria dos menores de grafos, desenvolvida por Robertson e Seymour, desempenha
um papel fundamental na caracterização estrutural de classes de grafos. Em particular,
a largura em árvore tornou-se uma ferramenta crucial na análise de grafos planares, por
permitir o desenvolvimento de algoritmos eficientes para problemas classicamente difíceis.
Esta dissertação tem como objetivo investigar a relação entre a planaridade e a largura em
árvores, destacando os principais conceitos, propriedades e teoremas que fundamentam a
estrutura de decomposições em árvores. Também são discutidos os teoremas de Kuratowski
e de Robertson-Seymour, bem como a noção de boa-quase-ordenação aplicada a árvores.
Através da análise de propriedades de grafos planares e da construção de decomposições
específicas, evidenciamos a importância da largura em árvores como medida de complexidade
estrutural em grafos planares.
Abstract
The theory of graph minors, developed by Robertson and Seymour, plays a central role in the structural characterization of graph classes. In particular, treewidth has become a key tool for analyzing planar graphs, enabling the design of efficient algorithms for classically hard problems. This dissertation aims to explore the relationship between planarity and treewidth, presenting essential concepts, properties, and theorems that underpin tree decompositions. We discuss Kuratowski’s and Robertson-Seymour’s theorems, as well as the notion of wellquasi-ordering for trees. Through an analysis of planar graph properties and specific tree decompositions, we highlight the importance of treewidth as a measure of structural complexity in planar graphs.
Assunto
Matemática – Teses, Teoria dos grafos – Teses, Árvores (Teoria dos grafos) – Teses, Grafos planares – Teses
Palavras-chave
Grafos menores, Grafos planares, Largura em árvores, Boa-quase-ordenação