An evolutionary algorithm for graph planarisation by vertex deletion
| Autor: | Dario Landa-Silva, Ademir Aparecido Constantino, Rodrigo Lankaites Pinheiro, Candido F. X. de Mendonça |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2014 |
| Předmět: |
Combinatorics
Factor-critical graph Mathematical optimization Computer science Graph power TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Wheel graph Neighbourhood (graph theory) Biconnected graph Butterfly graph Graph factorization Hypercube graph MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | ICEIS (1) |
| Popis: | A non-planar graph can only be planarized if it is structurally modified. This work presents a new heuristic algorithm that uses vertices deletion to modify a non-planar graph in order to obtain a planar subgraph. The proposed algorithm aims to delete a minimum number of vertices to achieve its goal. The vertex deletion number of a graph G = (V, E) is the smallest integer k � 0 such that there is an induced planar subgraph of G obtained by the removal of k vertices of G. Considering that the corresponding decision problem is NP-complete and an approximation algorithm for graph planarization by vertices deletion does not exist, this work proposes an evolutionary algorithm that uses a constructive heuristic algorithm to planarize a graph. This constructive heuristic has time complexity of O(n + m), where m = |V| and n = |E|, and is based on the PQ-trees data structure and on the vertex deletion operation. The algorithm performance is verified by means of case studies. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|