A note on the practicality of maximal planar subgraph algorithms

DOI10.1007/978-3-319-50106-2_28MaRDI QIDQ2961528zbMATH OpenOpenAlexFDO

Authors Markus Chimani, Karsten Klein, Tilo Wiedera

Publication date 21 February 2017

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

Full work available at URL https://arxiv.org/abs/1608.07505

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Planar graphs; geometric and topological aspects of graph theory (05C10)

Abstract: Given a graph $G$, the NP-hard Maximum Planar Subgraph problem (MPS) asks for a planar subgraph of $G$ with the maximum number of edges. There are several heuristic, approximative, and exact algorithms to tackle the problem, but---to the best of our knowledge---they have never been compared competitively in practice. We report on an exploratory study on the relative merits of the diverse approaches, focusing on practical runtime, solution quality, and implementation complexity. Surprisingly, a seemingly only theoretically strong approximation forms the building block of the strongest choice.

Recommendations

• Limits of greedy approximation algorithms for the maximum planar subgraph problem
• Two new approximation algorithms for the maximum planar subgraph problem
• Finding triangles for maximum planar subgraphs
• Exact algorithms for the maximum planar subgraph problem: new models and experiments
• Publication:4886062

Cites work

• scientific article; zbMATH DE number 3668651 (Why is no real title available?)
• A Better Approximation Algorithm for Finding Planar Subgraphs
• A new planarity test
• Advances in the planarization method: effective multiple edge insertions
• An experimental comparison of four graph drawing algorithms.
• Computing and Combinatorics
• Drawing directed acyclic graphs: an experimental study
• Efficient Extraction of Multiple Kuratowski Subdivisions
• Generating Random Regular Graphs Quickly
• Inserting multiple edges into a planar graph
• Limits of greedy approximation algorithms for the maximum planar subgraph problem
• Maximum planar subgraphs and nice embeddings: Practical layout tools
• Non-planar core reduction of graphs
• On the Cutting Edge: Simplified O(n) Planarity by Edge Addition

Cited in

(9)

• A new approximation algorithm for finding heavy planar subgraphs
• A subset spanner for Planar graphs, with application to subset TSP
• Exact algorithms for the maximum planar subgraph problem: new models and experiments
• Limits of greedy approximation algorithms for the maximum planar subgraph problem
• Finding triangles for maximum planar subgraphs
• A simulated annealing algorithm for the maximum planar subgraph problem
• scientific article; zbMATH DE number 871895 (Why is no real title available?)
• Cycles to the rescue! Novel constraints to compute maximum planar subgraphs fast
• Approximation Algorithms for the Maximum Induced Planar and Outerplanar Subgraph Problems

Describes a project that uses

Uses Software

• OGDF
• SteinLib

This page was built for publication: A note on the practicality of maximal planar subgraph algorithms

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