An algorithm and upper bounds for the weighted maximal planar graph problem

Abstract

In this paper, we investigate the weighted maximal planar graph (WMPG) problem. Given a complete, edge-weighted, simple graph, the WMPG problem involves finding a subgraph with the highest sum of edge weights that is maximal planar, namely, it can be embedded in the plane without any of its edges intersecting, and no additional edge can be added to the subgraph without violating its planarity. We present a new integer linear programming (ILP) model for this problem. We then develop a cutting-plane algorithm to solve the WMPG problem based on the proposed ILP model. This algorithm enables the problem to be solved more efficiently than previously reported algorithms. New upper bounds are also provided, which are useful in evaluating the quality of heuristic solutions or in generating initial solutions for meta-heuristics. Computational results are reported for a set of 417 test instances of size varying from 6 to 100 nodes including 105 instances from the literature and 312 randomly generated instances. The computational results indicate that instances with up to 24 nodes can be solved optimally in reasonable computational time and the new upper bounds for larger instances significantly improve existing upper bounds.

Keywords:

• facilities planning and design
• facility layout
• maximal planar graph problem
• integer linear programming
• cutting-plane algorithm
• upper bound

Acknowledgements

The authors would like to thank the referees for the valuable comments which helped improve the paper. The authors would like to thank Prof. Ibrahim H. Osman, from the American University of Beirut, who helped us by graciously sending us his test problems and giving his constructive advice.