A graph approximation heuristic for the vertex cover problem on planar graphs

The vertex cover problem is hard in general and remains so on planar graphs. On the other hand, it is always solvable on bipartite graphs. In this paper, the authors introduce a strategy which creates, from an arbitrary planar graph G, a minimum size bipartite homeomorph of G, say GÅH. They solve the vertex cover problem on GÅH and convert the solution to a cover on G. Tests on a set of sample graphs suggest that the resulting heuristic performs quite well.