Planarização de grafos por remoção de vértices.

• Ano de defesa: 2009
• Autor(a) principal: Pinheiro, Rodrigo Lankaites
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Estadual de Maringá; Brasil; Programa de Pós-Graduação em Ciência da Computação; UEM; Maringá; Departamento de Informática
• Palavras-chave em Português: Planarização de grafos; Grafos; Algoritmos em grafos; st-numeração; Algoritmo genético; Árvore-PQ.; Graph planarization; Graph algorithms; st-numbering; Genetic algorithm; PQ-tree; Ciências Exatas e da Terra; Ciência da Computação
• Link de acesso: http://repositorio.uem.br:8080/jspui/handle/1/2545

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.