Thumbnail Image
Publication

A GA-inspired approach to the reduction of edge crossings in force-directed layouts

Date
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.
Supervisor
Description
peer-reviewed
Publisher
Association for Computing Machinery
Citation
GECCO '16 Companion Proceedings of the 2016 on Genetic and Evolutionary Computation Conference Companion;pp. 89-90
Collections
Computer Science & Information Systems
Lero - The Science Foundation Ireland Research Centre for Software
Show all metadata
Files
Thumbnail Image
Eaton_2016_GA.pdf
Adobe PDF, 307.3 KB
Keywords
routing and layout, genetic algorithms, fitness evaluation, cominbatorial optimization, running time analysis
ULRR Identifiers
https://hdl.handle.net/10344/5395
 https://doi.org/10.34961/3229
Funding code
Funding Information
Science Foundation Ireland (SFI)
Sustainable Development Goals
External Link
License
Embedded videos