Please use this identifier to cite or link to this item:
Type: Artigo de periódico
Title: On Maximum Planar Induced Subgraphs
Author: Faria L.
de Figueiredo C.M.H.
Gravier S.
de Mendonca C.F.X.
Stolfi J.
Abstract: The nonplanar vertex deletion or vertex deletion vd (G) of a graph G is the smallest nonnegative integer k, such that the removal of k vertices from G produces a planar graph G′. In this case G′ is said to be a maximum planar induced subgraph of G. 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 nonnegative integer k, to decide whether vd (G) ≤ k is NP-complete. We prove that it is NP-complete to decide whether a maximum degree 3 graph G and a nonnegative integer k satisfy vd (G) ≤ k. We prove that unless P=NP there is no polynomial-time approximation algorithm with fixed ratio to compute the size of a maximum planar induced subgraph for graphs in general. We prove that it is Max SNP-hard to compute vd (G) when restricted to a cubic input G. Finally, we exhibit a polynomial-time frac(3, 4)-approximation algorithm for finding a maximum planar induced subgraph of a maximum degree 3 graph. © 2006 Elsevier B.V. All rights reserved.
Rights: fechado
Identifier DOI: 10.1016/j.dam.2006.03.021
Date Issue: 2006
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
2-s2.0-33745966136.pdf231.11 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.