Tabu search for the dynamic Bipartite Drawing Problem. (March 2018)

• Record Type: Journal Article
• Authors: Martí, Rafael; Martínez-Gavara, Anna; Sánchez-Oro, Jesús; Duarte, Abraham
• Is Part Of: Computers & operations research. Volume 91(2018)
• Page Start: 1
• Page End: 12
• Publication Date: 2018-03
• Subjects: Graph drawing -- Incremental drawing -- Bipartite graphs -- Dynamic representations; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2017.10.011
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: A new heuristic method for dynamic graph drawing. A mathematical programming formulation for bipartite graphs. An extensive experimental comparison with existing methods. Abstract: Drawings of graphs have many applications and they are nowadays well-established tools in computer science in general, and optimization in particular. Project scheduling is one of the many areas in which representation of graphs constitutes an important instrument. The experience shows that the main quality desired for drawings of graphs is readability, and crossing reduction is a fundamental aesthetic criterion to achieve it. Incremental or dynamic graph drawing is an emerging topic in this context, where we seek to preserve the layout of a graph over successive drawings. In this paper, we target the edge crossing reduction in the context of incremental graph drawing. Specifically, we apply a mathematical programming formulation and several heuristic methods based on the tabu search methodology to solve it. In line with the previous paper on this topic, we consider bipartite graphs in our experimentation. The extensive computational experiments with more than 1000 instances show the superiority of our proposals in both, quality and computing time.