6533b85ffe1ef96bd12c0f74

RESEARCH PRODUCT

Variable neighborhood descent for the incremental graph drawing

Manuel LagunaRafael MartíJesús Sánchez-oroAnna Martínez-gavaraAbraham Duarte

subject

021103 operations researchTheoretical computer sciencebusiness.industryApplied MathematicsGRASP0211 other engineering and technologies010103 numerical & computational mathematics02 engineering and technologyMachine learningcomputer.software_genre01 natural sciencesReadabilitySoftwareGraph drawingDiscrete Mathematics and CombinatoricsArtificial intelligenceForce-directed graph drawing0101 mathematicsbusinessGraph operationsMetaheuristiccomputerGreedy randomized adaptive search procedureMathematicsofComputing_DISCRETEMATHEMATICSMathematics

description

Abstract 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.

yearjournalcountryeditionlanguage
2017-04-01Electronic Notes in Discrete Mathematics
https://doi.org/10.1016/j.endm.2017.03.024