2016/08/26 by Markus Chimani, Chimani, Markus, Karsten Klein +3 · 2 citations
Computer Science · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.CC #cs.DS
paper · pdf · doi:10.48550/arxiv.1608.07505
Appears in the Proceedings of the 24th International Symposium on Graph Drawing and Network Visualization (GD 2016)
arxiv created 2016/08/26 · arxiv updated 2016/08/29
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.