.png){kind=icon}
.png){kind=icon}
Return
Heuristics for the Constrained Incremental Graph Drawing Problem
.png){kind=icon}
PRE
AI
DOI：10.1016/j.ejor.2018.10.017.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Visualization of information is a relevant topic in Computer Science, where graphs have become a standard representation model, and graph drawing is now a well-established area. Within this context, edge crossing minimization is a widely studied problem given its importance in obtaining readable representations of graphs. In this paper, we focus on the so-called incremental graph drawing problem, in which we try to preserve the user's mental map when obtaining successive drawings of the same graph. In particular, we minimize the number of edge crossings while satisfying some constraints required to preserve the position of vertices with respect to previous drawings. We propose heuristic methods to obtain high-quality solutions to this optimization problem in the short computational times required for graph drawing applications. We also propose a mathematical programming formulation and obtain the optimal solution for small and medium instances. Our extensive experimentation shows the merit of our proposal with respect to both optimal solutions obtained with CPLEX and heuristic solutions obtained with LocalSolver, a well-known black-box solver in combinatorial optimization. (C) 2018 Elsevier B.V. All rights reserved.
Keywords:
Heuristics
Metaheuristics
Combinatorial optimization
Graph drawing
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
6
Papers:
2.2W
Citations:
6.4W