Variable neighborhood descent for the incremental graph drawing

Graphs are used to represent reality in several areas of knowledge. Drawings of graphs have many applications, from project scheduling to software diagrams. The main quality desired for drawings of graphs is readability, and crossing reduction is a fundamental aesthetic criterion for a good representation of a graph. In this paper we target the edge crossing reduction in the context of incremental graph drawing, in which we want to preserve the layout of a graph over successive drawings. We propose a hybrid method based on the GRASP (Greedy Randomized Adaptive Search Procedure) and VND (Variable Neighborhood Descent) methodologies and compare it with previous methods via simulation.