Finding triangles for maximum planar subgraphs

DOI10.1007/978-3-319-53925-6_29MaRDI QIDQ2980925zbMATH OpenOpenAlexFDO

Authors Parinya Chalermsook, Andreas Schmid

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)

Recommendations

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

Cites work

• scientific article; zbMATH DE number 3668651 (Why is no real title available?)
• A Better Approximation Algorithm for Finding Planar Subgraphs
• A new approximation algorithm for finding heavy planar subgraphs
• An $O(m\log n)$-Time Algorithm for the Maximal Planar Subgraph Problem
• Handbook of Approximation Algorithms and Metaheuristics
• Handbook of graph drawing and visualization
• Large planar subgraphs in dense graphs
• Maximum series-parallel subgraph
• On the complexity of the approximation of nonplanarity parameters for cubic graphs
• The sizes of maximal planar, outerplanar, and bipartite planar subgraphs
• Two new approximation algorithms for the maximum planar subgraph problem

Cited in

(12)

• Use of MAX-CUT for Ramsey Arrowing of Triangles
• A note on the practicality of maximal planar subgraph algorithms
• Triangulating planar graphs while minimizing the maximum degree
• Exact algorithms for the maximum planar subgraph problem: new models and experiments
• Limits of greedy approximation algorithms for the maximum planar subgraph problem
• Finding Maximal Sets of Laminar 3-Separators in Planar Graphs in Linear Time
• Star-Struck by Fixed Embeddings: Modern Crossing Number Heuristics
• An improved algorithm for finding maximum outerplanar subgraphs
• Star-struck by fixed embeddings: modern crossing number heuristics
• scientific article; zbMATH DE number 1953077 (Why is no real title available?)
• Cycles to the rescue! Novel constraints to compute maximum planar subgraphs fast
• scientific article; zbMATH DE number 7559128 (Why is no real title available?)

This page was built for publication: Finding triangles for maximum planar subgraphs

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