An efficient metaheuristic for the K-page crossing number minimization problem

摘要

Graph layout problems refer to a family of optimization problems with relevant applications in VLSI design, information retrieval, numerical analysis, computational biology, or graph theory. In this paper, we focus on a variant where the graph is mapped over a specific structure referred to as book, which consists of a spine and a number of pages. Vertices of the graph are allocated in the spine, which is usually represented as a line, and edges are assigned to pages of the book, which are represented as half-planes that have the spine as its boundary. The experience shows that one of the main quality desired for layout of graphs is the minimization of edge crossing. The K-page crossing number minimization problem (KPMP) aims to reduce as much as possible the number of crossings between edges belonging to the same page. We propose the application of the VNS metaheuristic to efficiently solve the KPMP. Experiments show a remarkable improvement over the state-of-the-art procedures for a large set of instances, leading the proposed VNS algorithm as a promising strategy to solve this family of book drawing problems.