Resumo: Neste trabalho são propostos dois algoritmos que utilizam a operação de remoção de vértices para se obter um subgrafo planar. O número de remoção de vértices de um grafo G é o menor inteiro K_> 0 tal que exista um subgrafo planar induzido de G obtido pela remoção de K vértices de G. Considerando que o problema de decisão associado é NP-completo, este trabalho propõe o algoritmo heurístico VD-PLANARIZE de complexidade 0(m + n) para a planarização de grafos utilizando a estrutura de dados árvores-PQ, a operação de remoção de vértices e st-numeração. Outra proposta apresentada é a do algoritmo genético GAVD-PLANARIZE que busca melhorar as soluções do VD-PLANARIZE. Este trabalho apresenta detalhes da implementação dos dois algoritmos bem como os resultados que comprovam a complexidade teórica do VD-PLANARIZE e os bons resultados obtidos pelo GAVDPLANARIZE.
Abstract: This work proposes two algorithms that use the vertex deletion operation to obtain a planar subgraph. The vertex deletion number of a graph G is the lower integer K _> 0 such that there is an induced planar subgraph obtained by the removal of K vertexes from G. Considering that the associated decision problem is NP-complete, this work proposes the 0 (m + n) heuristic algorithm VD-PLANARIZE to planarize graphs using the PQ-tree data structure, the vertex deletion operation and st-numbering. Another proposal is the genetic algorithm GAVD-PLANARIZE that looks forward to improve the solutions obtained by the VD-PLANARIZE. This work presents details of the implementation of both algorithms as well as the results that aver the theoretical complexity of VD-PLANARIZE and show the good results obtained by the GAVD-PLANARIZE. |
