A Note on the Practicality of Maximal Planar Subgraph Algorithms

Chimani, Markus and Klein, Karsten and Wiedera, Tilo (2016) A Note on the Practicality of Maximal Planar Subgraph Algorithms. In: Graph Drawing and Network Visualization. GD 2016, September, 19. - 21., 2016 , pp. 357-364(Official URL: http://dx.doi.org/10.1007/978-3-319-50106-2_28).

Full text not available from this repository.


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.

Item Type: Conference Paper
Classifications: G Algorithms and Complexity > G.999 Others
M Methods > M.600 Planar
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1555

Actions (login required)

View Item View Item