Heuristics for the Constrained Incremental Graph Drawing Problem

Antonio Napoletano, Anna Martínez-Gavara, Paola Festa, Tommaso Pastore and Rafael Martí

European Journal of Operational Research, 2019, vol. 274, issue 2, 710-729

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

Keywords: Heuristics; Metaheuristics; Combinatorial optimization; Graph drawing (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221718308701
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:274:y:2019:i:2:p:710-729

DOI: 10.1016/j.ejor.2018.10.017

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().