Cycles to the Rescue! Novel Constraints to Compute Maximum Planar Subgraphs Fast

06/21/2018
by   Markus Chimani, et al.
0

The NP-hard Maximum Planar Subgraph problem asks for a planar subgraph H of a given graph G such that H has maximum edge cardinality. For more than two decades, the only known non-trivial exact algorithm was based on integer linear programming and Kuratowski's famous planarity criterion. We build upon this approach and present new constraint classes, together with a lifting of the polyhedron, to obtain provably stronger LP-relaxations, and in turn faster algorithms in practice. The new constraints take Euler's polyhedron formula as a starting point and combine it with considering cycles in G. This paper discusses both the theoretical as well as the practical sides of this strengthening.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset