A GRASP heuristic for the maximum-weight planar subgraph problem

Algorithms for the maximum-weight planar subgraph problem (MWPSP) are relevant
in a wide variety of applications, ranging from the analysis of financial data, facility layout, inte-
grated circuit design, systems biology, social systems, among others. The MWPSP is an NP-hard
problem and it is primarily addressed using heuristic algorithms, commonly utilizing construction
or improvement approaches. In this article, we present a customised GRASP (Greedy Random-
ized Adaptive Search Procedure) meta-heuristic designed to encompass both of these approaches.
During the construction phase, multiple feasible solutions are generated in parallel, whereas in the
improvement phase, the most optimal feasible solution obtained is subjected to further enhance-
ment through an equivalent dual 3-regular graph. Experimental validation demonstrates that the
proposed algorithm outperforms established heuristic methods, achieving superior solution quality
with improved running time performance.