Approximation Algorithms for the Maximum Induced Planar and Outerplanar Subgraph Problems

DOI10.7155/JGAA.00141zbMATH Open1161.68879OpenAlexW2143368979MaRDI QIDQ5301409FDOQ5301409

Authors: Kerri Morgan, Graham Farr 

Publication date: 19 January 2009

Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/55427

Recommendations

• A Better Approximation Algorithm for Finding Planar Subgraphs
• scientific article; zbMATH DE number 871895
• Approximation algorithms for NP-complete problems on planar graphs
• A note on the practicality of maximal planar subgraph algorithms
• Two new approximation algorithms for the maximum planar subgraph problem

zbMATH Keywords

planar subgraphlargest subset of vertices of a graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Cited In (9)

• A new approximation algorithm for finding heavy planar subgraphs
• Optimal approximation algorithms for maximum distance-bounded subgraph problems
• The maximum happy induced subgraph problem: bounds and algorithms
• Planarization and fragmentability of some classes of graphs
• An improved algorithm for finding maximum outerplanar subgraphs
• A Linear-Time Algorithm for Finding Induced Planar Subgraphs
• Exact algorithm for the maximum induced planar subgraph problem
• Title not available (Why is that?)
• Preprocessing for outerplanar vertex deletion: an elementary kernel of quartic size

This page was built for publication: Approximation Algorithms for the Maximum Induced Planar and Outerplanar Subgraph Problems

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