Tabu search for min-max edge crossing in graphs. (February 2020)

• Record Type: Journal Article
• Authors: Pastore, Tommaso; Martínez-Gavara, Anna; Napoletano, Antonio; Festa, Paola; Martí, Rafael
• Is Part Of: Computers & operations research. Volume 114(2020)
• Publication Date: 2020-02
• Subjects: Combinatorial optimization -- Graph drawing -- Metaheuristics; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2019.104830
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: Extension of the mathematical model in the case of multilayer hierarchical graphs. Implementation of a Tabu Search heuristic with a long term memory strategy. Adaptation of specific move evaluation function. Improvement of the state-of-the-art in solving the min-max graph-drawing problem. Abstract: Graph drawing is a key issue in the field of data analysis, given the ever-growing amount of information available today that require the use of automatic tools to represent it. Graph Drawing Problems (GDP) are hard combinatorial problems whose applications have been widely relevant in fields such as social network analysis and project management. While classically in GDPs the main aesthetic concern is related to the minimization of the total sum of crossing in the graph (min-sum), in this paper we focus on a particular variant of the problem, the Min-Max GDP, consisting in the minimization of the maximum crossing among all egdes. Recently proposed in scientific literature, the Min-Max GDP is a challenging variant of the original min-sum GDP arising in the optimization of VLSI circuits and the design of interactive graph drawing tools. We propose a heuristic algorithm based on the tabu search methodology to obtain high-quality solutions. Extensive experimentation on an established benchmark set with both previous heuristics and optimal solutions shows that our method is able to obtain excellent solutions in short computation time.