Menores de grafos: largura em árvores de 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.