On maximum planar induced subgraphs

DOI10.1016/J.DAM.2006.03.021zbMATH Open1107.68063OpenAlexW2021903733MaRDI QIDQ2500525FDOQ2500525

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

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

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)

Cites Work

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

Cited In (8)

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

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)