Limits of Greedy Approximation Algorithms for the Maximum Planar Subgraph Problem

DOI10.1007/978-3-319-44543-4_26zbMath1478.68224OpenAlexW2537735054MaRDI QIDQ2819516

Ivo Hedtke, Tilo Wiedera, Markus Chimani

Publication date: 29 September 2016

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-44543-4_26

Mathematics Subject Classification ID

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

Related Items (2)

A Note on the Practicality of Maximal Planar Subgraph Algorithms ⋮ Unnamed Item

Cites Work

• Analysis of heuristics for finding a maximum weight planar subgraph
• A new planarity test
• On the Cutting Edge: Simplified O(n) Planarity by Edge Addition
• Efficient Planarity Testing
• A Better Approximation Algorithm for Finding Planar Subgraphs
• Computing and Combinatorics
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Limits of Greedy Approximation Algorithms for the Maximum Planar Subgraph Problem