On maximum planar induced subgraphs

DOI10.1016/J.DAM.2006.03.021MaRDI QIDQ2500525zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 17 August 2006

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2006.03.021

zbMATH Keywords

cubic graphstopological graph theorynonapproximabilitymaximum planar induced subgraphnonplanar edge deletionnonplanar vertex deletionNP-complete and Max SNO-hard problemsplanarity invariants

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Planar graphs; geometric and topological aspects of graph theory (05C10)

Recommendations

• A Better Approximation Algorithm for Finding Planar Subgraphs
• Exact algorithm for the maximum induced planar subgraph problem
• scientific article; zbMATH DE number 871895
• Node-and edge-deletion NP-complete problems
• On the complexity of the approximation of nonplanarity parameters for cubic graphs

Cites work

• scientific article; zbMATH DE number 3668651 (Why is no real title available?)
• scientific article; zbMATH DE number 1256635 (Why is no real title available?)
• scientific article; zbMATH DE number 1256636 (Why is no real title available?)
• A Better Approximation Algorithm for Finding Planar Subgraphs
• A proof of the four color theorem
• An Approximation Algorithm for the Maximum Independent Set Problem on Planar Graphs
• Crossing Number is NP-Complete
• Edge-Deletion Problems
• Node-and edge-deletion NP-complete problems
• On the complexity of the approximation of nonplanarity parameters for cubic graphs
• Optimization, approximation, and complexity classes
• SPLITTING NUMBER is NP-complete
• The graph genus problem is NP-complete
• The non planar vertex deletion of \(C_n\times C_m\).

Cited in

(8)

• The non planar vertex deletion of \(C_n\times C_m\).
• An Application of Duality to Edge-Deletion Problems
• Boundary graph classes for some maximum induced subgraph problems
• Exact algorithm for the maximum induced planar subgraph problem
• Planarization and acyclic colorings of subcubic claw-free graphs
• Obtaining a Planar Graph by Vertex Deletion
• Maximal planar subgraphs of fixed girth in random graphs
• Lossy planarization: a constant-factor approximate kernelization for planar vertex deletion

This page was built for publication: On maximum planar induced subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2500525)