GRASP with Path Relinking for the Constrained Incremental Graph Drawing Problem

Graph Drawing is a well-established area in Computer Science, with applications from scheduling to software diagrams. The main quality desired for drawings is readability, and edge crossing minimization is a well-recognized method for a good representation of them. This work focuses in incremental graph drawing problems, with the aim to minimize the number of edge crossings while satisfying some constraints to preserve the absolute position of the vertices in previous drawings. We propose a mathematical model and a GRASP (Greedy Randomized Adaptive Search Procedure) with PR (Path Relinking) methodology to solve this problem. Finally, we compare our methodology with CPLEX and heuristic solutions obtained by a well-known blackbox solver, LocalSolver.