Two new approximation algorithms for the maximum planar subgraph problem

MaRDI QIDQ3615285zbMATH OpenFDO

Authors Timo Poranen

Publication date 19 March 2009

zbMATH Keywords

approximation algorithmmaximum outerplanar subgraphmaximum planar subgraphouterthicknessthicknesstriangular cactus heuristic

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Recommendations

• A Better Approximation Algorithm for Finding Planar Subgraphs
• scientific article; zbMATH DE number 871895
• scientific article; zbMATH DE number 910888
• A simulated annealing algorithm for the maximum planar subgraph problem
• Limits of greedy approximation algorithms for the maximum planar subgraph problem

Cited in

(12)

• A new approximation algorithm for finding heavy planar subgraphs
• Limits of greedy approximation algorithms for the maximum planar subgraph problem
• A subset spanner for Planar graphs, with application to subset TSP
• A note on the practicality of maximal planar subgraph algorithms
• Finding triangles for maximum planar subgraphs
• On the k-restricted structure ratio in planar and outerplanar graphs
• A Better Approximation Algorithm for Finding Planar Subgraphs
• scientific article; zbMATH DE number 871895 (Why is no real title available?)
• Approximation Algorithms for the Maximum Induced Planar and Outerplanar Subgraph Problems
• An improved algorithm for finding maximum outerplanar subgraphs
• Finding large planar subgraphs and large subgraphs of a given genus
• Local optimization algorithms for maximum planar subgraph

This page was built for publication: Two new approximation algorithms for the maximum planar subgraph problem

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