Heuristics for the min–max arc crossing problem in graphs. (1st November 2018)

• Record Type: Journal Article
• Authors: Martí, Rafael; Campos, Vicente; Hoff, Arild; Peiró, Juanjo
• Is Part Of: Expert systems with applications. Volume 109(2018)
• Page Start: 100
• Page End: 113
• Publication Date: 2018-11-01
• Subjects: Graph drawing expert system -- Metaheuristics -- Crossing reduction -- Iterated greedy; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2018.05.008
• Languages: English
• ISSNs: 0957-4174

Abstract

Highlights: A heuristic method to improve the readability of graphs. A crossing reduction method for graph drawing expert systems. A mathematical programming formulation for the min–max arc crossing problem. An empirical comparison with the best existing method, including expert systems. Extensive computational results and statistical testing to compare methods. Abstract: In this paper, we study the visualization of complex structures in the context of automatic graph drawing. Constructing geometric representations of combinatorial structures, such as networks or graphs, is a difficult task that requires an expert system. The automatic generation of drawings of graphs finds many applications from software engineering to social media. The objective of graph drawing expert systems is to generate layouts that are easy to read and understand. This main objective is achieved by solving several optimization problems. In this paper we focus on the most important one: reducing the number of arc crossings in the graph. This hard optimization problem has been studied extensively in the last decade, proposing many exact and heuristic methods to minimize the total number of arc crossings. However, despite its practical significance, the min–max variant in which the maximum number of crossings over all edges is minimized, has received very little attention. We propose new heuristic methods based on the strategic oscillation methodology to solve this NP-hard optimization problem. Our experimentation shows that the new method compares favorably with the existing ones, implemented in current graph drawing expert systems. Therefore, a direct application of our findings will improve these functionality (i.e., crossing reduction) of drawing systems.