Rodrigo Lankaites Pinheiro
An evolutionary algorithm for graph planarisation by vertex deletion
Pinheiro, Rodrigo Lankaites; Constantino, Ademir Aparecido; de Mendonca, Candido F. X.; Landa-Silva, Dario
Authors
Ademir Aparecido Constantino
Candido F. X. de Mendonca
Professor DARIO LANDA SILVA DARIO.LANDASILVA@NOTTINGHAM.AC.UK
PROFESSOR OF COMPUTATIONAL OPTIMISATION
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 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.
Citation
Pinheiro, R. L., Constantino, A. A., de Mendonca, C. F. X., & Landa-Silva, D. An evolutionary algorithm for graph planarisation by vertex deletion. Presented at 16th International Conference on Enterprise Information Systems (ICEIS 2014)
Conference Name | 16th International Conference on Enterprise Information Systems (ICEIS 2014) |
---|---|
End Date | Apr 30, 2014 |
Publication Date | Jan 1, 2014 |
Deposit Date | Jan 22, 2016 |
Publicly Available Date | Jan 22, 2016 |
Peer Reviewed | Peer Reviewed |
Keywords | evolutionary algorithms, graphical data representation |
Public URL | https://nottingham-repository.worktribe.com/output/999568 |
Publisher URL | http://www.scitepress.org/DigitalLibrary/Link.aspx?doi=10.5220/0004883704640471 |
Additional Information | Published in: Proceedings of the 16th International Conference on Enterprise Information Systems, ISBN 9789897580277, pages 464-471. DOI: 10.5220/0004883704640471 |
Files
dls_iceis2014.pdf
(898 Kb)
PDF
You might also like
Local-global methods for generalised solar irradiance forecasting
(2024)
Journal Article
UAV Path Planning for Area Coverage and Energy Consumption in Oil and Gas Exploration Environment
(2023)
Presentation / Conference Contribution
Towards Blockchain-based Ride-sharing Systems
(2021)
Presentation / Conference Contribution
Downloadable Citations
About Repository@Nottingham
Administrator e-mail: discovery-access-systems@nottingham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search