On maximum planar induced subgraphs
| Autor: | Jorge Stolfi, Luerbio Faria, Sylvain Gravier, Candido F. X. de Mendonça, Celina M. H. de Figueiredo |
|---|---|
| Rok vydání: | 2006 |
| Předmět: |
Topological graph theory
Factor-critical graph Discrete mathematics NP-complete and Max SNP-hard problems Degree (graph theory) Applied Mathematics Neighbourhood (graph theory) Induced subgraph Maximum planar induced subgraph Combinatorics Nonplanar vertex deletion Nonplanar edge deletion Graph power Planarity invariants Discrete Mathematics and Combinatorics Induced subgraph isomorphism problem Bound graph Cubic graphs Nonapproximability Mathematics Universal graph |
| Zdroj: | Discrete Applied Mathematics. 154(13):1774-1782 |
| ISSN: | 0166-218X |
| DOI: | 10.1016/j.dam.2006.03.021 |
| Popis: | 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 34-approximation algorithm for finding a maximum planar induced subgraph of a maximum degree 3 graph. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect