Nonplanar vertex deletion: maximum degree thresholds for NP/Max SNP-hardness and a -approximation for finding maximum planar induced subgraphs

Autor:	Luerbio Faria, Sylvain Gravier, Celina M. H. de Figueiredo, Jorge Stolfi, Candido F. X. de Mendonça
Rok vydání:	2004
Předmět:	Combinatorics Factor-critical graph Discrete mathematics Graph bandwidth Degree (graph theory) Graph power Applied Mathematics Neighbourhood (graph theory) Discrete Mathematics and Combinatorics Cubic graph Bound graph Regular graph Mathematics
Zdroj:	Electronic Notes in Discrete Mathematics. 18:121-126
ISSN:	1571-0653
DOI:	10.1016/j.endm.2004.06.019
Popis:	The non planar vertex deletion v d ( G ) , of a graph G is the smallest positive integer k, such that the removal of k vertices from G produces a planar graph. We solve a problem proposed by Yannakakis: find the threshold for the maximum degree of a graph G such that, given a graph G and a positive integer k, to decide whether v d ( G ) ≤ k is NP-complete. We prove that it is NP-complete to decide whether a maximum degree 3 graph G and a positive integer k satisfy v d ( G ) ≤ k . We prove that to compute v d ( G ) is Max SNP-hard when restricted to a cubic input G. We exhibit a polynomial 3 4 -approximation algorithm for finding a maximum planar induced subgraph of a maximum degree 3 graph.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::91325280cbafcd6fbbb7fc2a8a060fdb https://doi.org/10.1016/j.endm.2004.06.019 Zobrazit plný text záznamu Full Text from ScienceDirect