Finding Triangles for Maximum Planar Subgraphs

DOI10.1007/978-3-319-53925-6_29zbMath1485.68310OpenAlexW2625058834MaRDI QIDQ2980925

Andreas Schmid, Parinya Chalermsook

Publication date: 5 May 2017

Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-53925-6_29

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items

Star-Struck by Fixed Embeddings: Modern Crossing Number Heuristics, Star-struck by fixed embeddings: modern crossing number heuristics, An improved algorithm for finding maximum outerplanar subgraphs, Unnamed Item, Unnamed Item, Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new approximation algorithm for finding heavy planar subgraphs
• On the complexity of the approximation of nonplanarity parameters for cubic graphs
• The sizes of maximal planar, outerplanar, and bipartite planar subgraphs
• Maximum series-parallel subgraph
• Large planar subgraphs in dense graphs
• Handbook of Approximation Algorithms and Metaheuristics
• A Better Approximation Algorithm for Finding Planar Subgraphs
• An $O(m\log n)$-Time Algorithm for the Maximal Planar Subgraph Problem