Approximation Algorithms for the Maximum Induced Planar and Outerplanar Subgraph Problems

DOI10.7155/JGAA.00141MaRDI QIDQ5301409zbMATHOpenAlexFDO

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

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)

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

Cited in

(11)

• Preprocessing for outerplanar vertex deletion: an elementary kernel of quartic size
• Optimal approximation algorithms for maximum distance-bounded subgraph problems
• Limits of greedy approximation algorithms for the maximum planar subgraph problem
• A new approximation algorithm for finding heavy planar subgraphs
• An improved algorithm for finding maximum outerplanar subgraphs
• Finding large planar subgraphs and large subgraphs of a given genus
• Planarization and fragmentability of some classes of graphs
• A linear-time algorithm for finding induced planar subgraphs
• The maximum happy induced subgraph problem: bounds and algorithms
• Exact algorithm for the maximum induced planar subgraph problem
• scientific article; zbMATH DE number 2084267 (Why is no real title available?)

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)