K-page crossing number minimization problem

Alberto Herrán, J. Manuel Colmenar, Abraham Duarte

https://www.sciencedirect.com/science/article/abs/pii/S0950705120305050

The objective is to map a general graph into a book with exactly K pages, minimizing the number of edge crossings in each page. A particular solution of this problem is then obtained by placing the vertices of a graph along the spine and assigning the edges connecting the vertices to the different pages of the book.

Instances and results

In order to favor future comparisons, we provide here both the instances used in the paper as well as the obtained results including cost and execution time.