@article{lue-fig-gra-men-sto-06-maxpl,
  author = {Luerbio Faria and Celina M. Herrera de Figueiredo and Sylvain Gravier and Candido Ferreira Xavier de {Mendon{\c{c}}a Neto} and Jorge Stolfi},
  title = {On Maximum Planar Induced Subgraphs},
  journal = {Discrete Applied Mathematics},
  volume = {154},
  number = {13},
  pages = {1774--1782},
  year = 2006,
  month = aug,
  doi = {doi:10.1016/j.dam.2006.03.021},
  citations = {WoS/2021: 3},
  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 $vg(G) \leq 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 $vg(G) \leq 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 -approximation algorithm for finding a maximum planar induced subgraph of a maximum degree 3 graph.}
}