A note on the practicality of maximal planar subgraph algorithms

DOI10.1007/978-3-319-50106-2_28zbMATH Open1478.68225arXiv1608.07505OpenAlexW2507175560MaRDI QIDQ2961528FDOQ2961528

Authors: Markus Chimani, Karsten Klein, Tilo Wiedera 

Publication date: 21 February 2017

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

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.

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

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

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)

Cites Work

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

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
• Title not available (Why is that?)
• Cycles to the rescue! Novel constraints to compute maximum planar subgraphs fast
• Approximation Algorithms for the Maximum Induced Planar and Outerplanar Subgraph Problems

Uses Software

• SteinLib
• OGDF

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)