An Analysis of Some Heuristics for the Maximum Planar Subgraph Problem

Robert Cimikowski
Computer Science Department
Montana State University,
Bozeman, MT 59717, USA
e-mail: cimo@cs.montana.edu

We analyze several heuristics for finding a maximum planar subgraph
of a nonplanar graph.  The problem is NP-hard, although several
heuristics which perform well in practice have been reported.
In particular, we compare the two principle methods, based on path
addition and vertex addition, respectively, with an incremental
method, a ``cycle packing" approach, and a branch-and-cut algorithm.
For the incremental method, the path addition method, and an edge
addition method, we prove theoretical worst-case performance bounds
of 1/3.  We also present an empirical analysis of some of the
heuristics.  Our results indicate that the branch-and-cut method
yields the best solutions.