Implicações geométricas e topológicas da planaridade em grafos

Abstract

O objetivo principal deste trabalho é tratar as implicações geométricas e topológicas da planaridade, destacando a influência desse conceito em problemas geométricos fundamentais. Tais problemas são derivados da fórmula de Euler e suas diversas aplicações. Também problemas topológicos, como o problema de coloração de mapas, são estudados na dissertação. A teoria de grafos tem extensiva utilização em matemática aplicada, pois demonstra ser uma poderosa ferramenta para a modelagem de diversas situações reais em física, química, biologia, engenharia elétrica e pesquisa operacional. Tanto em problemas práticos como em problemas teóricos tem-se o fato que a maioria das aplicações admitem métodos de resolução mais eficientes se o grafo associado for planar. A determinação da planaridade de um grafo é importante em diversas aplicações na indústria, engenharia e outras. Um aspecto neste estudo é que a planaridade é uma propriedade preservada mediante o isomorfismo de grafos. Também apresenta-se duas caracterizações da planaridade, uma devido a Kuratowski e outra devido a Wagner. São dois resultados clássicos da teoria de grafos, que identificam condições necessárias e suficientes para um dado grafo ser planar, e cujas técnicas de demonstração são ainda importantes em combinatória.

The main goal of this work is to treat the geometrical and topological implications of planarity, highlighting the infl.uence of t his concept over fundamental problems. Such problems are derived from the Euler's formula and its applications. Topological problems, such as map colouring, are also dealt with in this thesis. Graph theory has extensive use in applied mathematics, because it shows to be a powerful tool for modelling real situations in physics, chemistry, biology, electrical engineering and operational research. In theory, as well as in practical problems, it is the fact most applications admit more efficient solution methods if the associated graph is planar. The determination of the planarity of a graph is important in various applications in industry, engineering and others. An aspect of this survey is that planarity is an invariant property preserved throu~h graph isomorphisms. It is also presented two characterizations of planarity. One is due to Kuratowski and the other is due to Wagner. These are two classical results of graph theory, that identify necessary and sufficient conditions for a graph to be planar, whose t echniques are still important in combinatorics.