| On 2003-06-09 at 15:00:00 (Brussels Time) |
Abstract
Given a non-planar sparse graph G (N,A), the graph planarization (GP) problem seeks to remove the minimum number of arcs (Ap) from the graph G to make the remaining sub-graph GP=(N, A-Ap) is planar. In this paper, we will introduce a new integer programming formulation for the problem. We then design an exact branch and bound procedure, classical heuristics and recent meta-heuristics based on LP relaxation for the problem. Computational results provided optimal solutions for small sized instances, good approximate solutions for small to large instances. Future search directions will be discussed.
Keywords
Integer programming, graph planarization, Heuristics and meta-heuristics
