An Evolutionary Algorithm for Graph Planarisation by Vertex Deletion

Rodrigo Lankaites Pinheiro, Ademir Aparecido Constantino, Candido F. X. de Mendonça, Dario Landa-Silva

2014

Abstract

A non-planar graph can only be planarised 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 planarisation by vertices deletion does not exist, this work proposes an evolutionary algorithm that uses a constructive heuristic algorithm to planarise 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.

Paper Citation

in Harvard Style

Lankaites Pinheiro R., Constantino A., F. X. de Mendonça C. and Landa-Silva D. (2014). An Evolutionary Algorithm for Graph Planarisation by Vertex Deletion . In Proceedings of the 16th International Conference on Enterprise Information Systems - Volume 1: ICEIS, ISBN 978-989-758-027-7, pages 464-471. DOI: 10.5220/0004883704640471

in Bibtex Style

@conference{iceis14,
author={Rodrigo Lankaites Pinheiro and Ademir Aparecido Constantino and Candido F. X. de Mendonça and Dario Landa-Silva},
title={An Evolutionary Algorithm for Graph Planarisation by Vertex Deletion},
booktitle={Proceedings of the 16th International Conference on Enterprise Information Systems - Volume 1: ICEIS,},
year={2014},
pages={464-471},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0004883704640471},
isbn={978-989-758-027-7},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 16th International Conference on Enterprise Information Systems - Volume 1: ICEIS,
TI - An Evolutionary Algorithm for Graph Planarisation by Vertex Deletion
SN - 978-989-758-027-7
AU - Lankaites Pinheiro R.
AU - Constantino A.
AU - F. X. de Mendonça C.
AU - Landa-Silva D.
PY - 2014
SP - 464
EP - 471
DO - 10.5220/0004883704640471