Problemas em grafos dinâmicos: outerplanaridade e aplicações

Abstract

Algoritmos em grafos desempenham um importante papel na área de computação. Muitos problemas aplicados ao mundo real podem ser modelados como um grafo e resolvidos utilizando-se algoritmos que exploram propriedades pertencentes aos mesmos. Nesse trabalho, o interesse principal é enfatizar os algoritmos aplicados a grafos dinâmicos, ou seja, grafos que se modificam conforme o passar do tempo (nesses tipos de algoritmos, a solução para o problema evita com que seja necessário efetuar um novo cálculo de todas as informações acerca do grafo após determinada operação de atualização no mesmo). Mais especificamente, estamos interessados em algoritmos para realizar a manutenção da outerplanaridade (um grafo é outerplanar se é planar e possui uma imersão no plano, sem cruzamento de arestas, de maneira tal que seus vértices pertencem à face exterior) em um grafo dinâmico. Nesta dissertação implementaremos um algoritmo completamente dinâmico para resolver o problema da manutenção da outerplanaridade em grafos dinâmicos.