An evolutionary algorithm for graph planarisation by vertex deletion
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...
| Main Authors: | , , , |
|---|---|
| Format: | Conference or Workshop Item |
| Published: |
Scitepress
2014
|
| Subjects: | |
| Online Access: | https://eprints.nottingham.ac.uk/31330/ |
| _version_ | 1848794178677374976 |
|---|---|
| author | Pinheiro, Rodrigo Lankaites Constantino, Ademir Aparecido de Mendonca, Candido F. X. Landa-Silva, Dario |
| author_facet | Pinheiro, Rodrigo Lankaites Constantino, Ademir Aparecido de Mendonca, Candido F. X. Landa-Silva, Dario |
| author_sort | Pinheiro, Rodrigo Lankaites |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | 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 NPcomplete 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 it is based on the PQ-trees data structure and on the vertex deletion operation. The algorithm performance is verified by means of case studies. |
| first_indexed | 2025-11-14T19:12:04Z |
| format | Conference or Workshop Item |
| id | nottingham-31330 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| last_indexed | 2025-11-14T19:12:04Z |
| publishDate | 2014 |
| publisher | Scitepress |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-313302020-05-04T20:17:34Z https://eprints.nottingham.ac.uk/31330/ An evolutionary algorithm for graph planarisation by vertex deletion Pinheiro, Rodrigo Lankaites Constantino, Ademir Aparecido de Mendonca, Candido F. X. Landa-Silva, Dario 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 NPcomplete 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 it is based on the PQ-trees data structure and on the vertex deletion operation. The algorithm performance is verified by means of case studies. Scitepress 2014 Conference or Workshop Item PeerReviewed Pinheiro, Rodrigo Lankaites, Constantino, Ademir Aparecido, de Mendonca, Candido F. X. and Landa-Silva, Dario (2014) An evolutionary algorithm for graph planarisation by vertex deletion. In: 16th International Conference on Enterprise Information Systems (ICEIS 2014), 27-30 April, 2014, Lisbon, Portugal. evolutionary algorithms graphical data representation http://www.scitepress.org/DigitalLibrary/Link.aspx?doi=10.5220/0004883704640471 |
| spellingShingle | evolutionary algorithms graphical data representation Pinheiro, Rodrigo Lankaites Constantino, Ademir Aparecido de Mendonca, Candido F. X. Landa-Silva, Dario An evolutionary algorithm for graph planarisation by vertex deletion |
| title | An evolutionary algorithm for graph planarisation by vertex deletion |
| title_full | An evolutionary algorithm for graph planarisation by vertex deletion |
| title_fullStr | An evolutionary algorithm for graph planarisation by vertex deletion |
| title_full_unstemmed | An evolutionary algorithm for graph planarisation by vertex deletion |
| title_short | An evolutionary algorithm for graph planarisation by vertex deletion |
| title_sort | evolutionary algorithm for graph planarisation by vertex deletion |
| topic | evolutionary algorithms graphical data representation |
| url | https://eprints.nottingham.ac.uk/31330/ https://eprints.nottingham.ac.uk/31330/ |