Back to the program.
Graph Planarization: Modeling and Solving.
Ibrahim H. Osman
School of Business
American University of Beirut
Beirut, Lebanon


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.


Integer programming, graph planarization, Heuristics and meta-heuristics