We report on our findings using a genetic algorithm (GA) as a preprocessing step for force-directed graph drawings to find a smart initial vertex layout (instead of a random initial layout) to decrease the number of edge crossings in the graph. We demonstrate that the initial layouts found by our GA improve the chances of finding better results in terms of the number of edge crossings, especially for sparse graphs and star-shaped graphs. In particular we demonstrate a reduction in edge-crossings for the class of star-shaped graphs by using our GA over random vertex placement in the order of 3:1.
Paper
Full text
A GA-Inspired Approach to the Reduction of Edge Crossings in Force-Directed Layouts
Semantic Scholar · Computer Science · 2016
Abstract
We report on our findings using a genetic algorithm (GA) as a preprocessing step for force-directed graph drawings to find a smart initial vertex layout (instead of a random initial layout) to decrease the number of edge crossings in the graph. We demonstrate that the initial layouts found by our GA improve the chances of finding better results in terms of the number of edge crossings, especially for sparse graphs and star-shaped graphs. In particular we demonstrate a reduction in edge-crossings for the class of star-shaped graphs by using our GA over random vertex placement in the order of 3:1.