Planarização de grafos por remoção de vértices. - Pinheiro, Rodrigo Lankaites (2009)
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.