Heuristics for the Maximum Outerplanar Subgraph Problem

Determining the maximum outerplanar subgraph of a given graph is known to be an NP-complete problem. In the literature there are no earlier experiment on approximating the maximum outerplanar subgraph problem. In this paper we compare solution quality and running times of different heuristics for finding maximum outerplanar subgraphs. We compare a greedy heuristic against a triangular cactus heuristic and its greedy variation. We also use the solutions from the greedy heuristics as initial solutions for a simulated annealing algorithm.The main experimental result is that simulated annealing with initial solution taken from the greedy triangular cactus heuristic yields the best known approximations for the maximum outerplanar subgraph problem.Work funded by the Tampere Graduate School in Information Science and Engineering (TISE) and supported by the Academy of Finland (Project 51528).