Remember Me
Or use your Academic/Social account:


Or use your Academic/Social account:


You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.


Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message


Verify Password:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Pinheiro, Rodrigo Lankaites; Constantino, Ademir Aparecido; de Mendonca, Candido F. X.; Landa-Silva, Dario (2014)
Publisher: Scitepress
Languages: English
Types: Unknown

Classified by OpenAIRE into

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.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • Battista, G. D. and Nardelli, E. (1988). Hierarchies and planarity theory. IEEE Transactions on Systems, Man, and Cybernetics, (18):10351046.
    • Booth, K. S. and Lueker, G. S. (1976). Testing for the consecutive ones property, interval graphs, and graph planarity using pq-tree algorithms. Journal of Computer and System Sciences, 13(3):335 - 379.
    • Chiba, T., Nishioka, I., and Shirakawa, I. (1979). An algorithm of maximal planarization of graphs. In Proc. 1979 IEEE Symp. on Circuits and Sys, pages 649-652.
    • Constantino, A. A., de Mendonc¸a, C. F. X., and Pinheiro, R. L. (2011). Um algoritmo heurstico de complexidade linear para planarizac¸o de grafos por remoc¸o de vrtices. In In Proc. XLIII Simpo´sio Brasileiro de Pesquisa Operacional, XLIII SBPO, pages 1-11.
    • de Figueiredo, C. M. H., Faria, L., and Mendonc¸a, C. F. X. (1999). Optimal node-degree bounds for the complexity of nonplanarity parameters. In Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, SODA '99, pages 887-888.
    • Eades, P. and de Mendonc¸a, C. F. X. (1993). Heuristics for planarization by vertex splitting. In In Proc. ALCOM Int. Workshop on Graph Drawing, GD'93, pages 83- 85.
    • Even, S. (2011). Graph Algorithms. Cambridge University Press, New York, NY, USA, 2nd edition.
    • Even, S. and Tarjan, R. E. (1976). Computing an stnumbering. Theoretical Computer Science, 2(3):339 - 344.
    • Faria, L., de Figueiredo, C., and Mendonc¸a, C. (2001a). Splitting number is np-complete. Discrete Applied Mathematics, 108(12):65 - 83. ¡ce:title¿Workshop on Graph Theoretic Concepts in Computer Science¡/ce:title¿.
    • Faria, L., de Figueiredo, C. M. H., and de Mendonc¸a Neto, C. F. X. (2001b). On the complexity of the approximation of nonplanarity parameters for cubic graphs. pages 18-21.
    • Faria, L., de Figueiredo, C. M. H., and de Mendonc¸a Neto, C. F. X. (2004). On the complexity of the approximation of nonplanarity parameters for cubic graphs. Discrete Applied Mathematics, 141(1-3):119-134. L., de Figueiredo, C. M. H., Gravier, S., de Mendonc¸a, C. F., and Stolfi, J. (2006). On maximum planar induced subgraphs. Discrete Applied Mathematics, 154(13):1774 - 1782.
    • Fisher, G. and Wing, O. (1966). Computer recognition and extraction of planar graphs from the incidence matrix. Circuit Theory, IEEE Transactions on, 13(2):154- 163.
    • Garey, M. and Johnson, D. (1983). Crossing number is npcomplete. SIAM Journal on Algebraic Discrete Methods, 4(3):312-316.
    • Gibbons, A. (1985). Algorithmic Graph Theory. Cambridge University Press.
    • Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1st edition.
    • Jayakumar, R., Thulasiraman, K., and Swamy, M. (1989). O(n2) algorithms for graph planarization. ComputerAided Design of Integrated Circuits and Systems, IEEE Transactions on, 8(3):257-267.
    • Lempel, A., Even, S., and Cederbaum, I. (1967). An algorithm for planarity testing of graphs. In Theory of Graphs, International Symposium, pages 215-232.
    • Liu, P. C. and Geldmacher, R. C. (1977). On the deletion of nonplanar edges of a graph. In Proc. 10th S-E Conf. Combinatorics, Graph Theory, and Computing, Boca, pages 727-738.
    • Marek-Sadowska, M. (1978). Planarization algorithms for integrated circuits engineering. In in Proc. IEEE International Symposium on Circuits and Systems, pages 919-923.
    • Ozawa, T. and Takahashi, H. (1981). A graph-planarization algorithm and its applications to random graphs. In in Graph Theory and Algorithms, Lecture Notes in Computer Science, pages 95-107. Springer-Verlag.
    • Pasedach, K. (1976). Criterion and algorithms for determination of bipartite subgraphs and their application to planarization of graphs. Graphen-Sprach. Algorithm. Graphen, 1. Fachtag. graphen-theor. Konz. Inf., Berlin(West) 1975, 175-183 (1976).
    • Pinheiro, R. L., Constantino, A. A., and de Mendonc¸a and, C. F. X. (2012). Um algoritmo evolutivo para planarizac¸a˜o de grafos por remoc¸a˜o de ve´rtices. In In Proc. XLIV Simpo´sio Brasileiro de Pesquisa Operacional, XLIV SBPO, pages 1-12.
    • Robertson, N. and Seymour, P. (1995). Graph minors .xiii. the disjoint paths problem. Journal of Combinatorial Theory, Series B, 63(1):65 - 110.
    • Yannakakis, M. (1978). Node-and edge-deletion npcomplete problems. In Proceedings of the tenth annual ACM symposium on Theory of computing, STOC '78, pages 253-264, New York, NY, USA. ACM.
  • No related research data.
  • No similar publications.

Share - Bookmark

Cite this article