Tight Runtime Bounds for Evolutionary Algorithms on Sorting and Crossing Minimisation for Layered Graph Drawings

Abstract Graph Drawing aims to make graphs visually comprehensible while faithfully representing their structure. In layered drawings, each vertex is drawn on one of k given horizontal lines and edges are drawn as y -monotone curves. A key ingredient for constructing such drawings is the One-Sided Bipartite Crossing Minimisation (OBCM) problem: given two layers of a bipartite graph and a fixed horizontal order of the vertices on the first layer, the task is to order the vertices on the second layer to minimise the number of edge crossings. We analyse the performance of simple evolutionary algorithms for OBCM and compare different operators for permutations: exchanging two elements, swapping adjacent elements and jumping an element to a new position. We show that on instances that can be drawn crossing-free, OBCM corresponds to a generalised sorting problem. We provide novel and tight lower bounds of $$\Omega (n^2 \log n)$$ for sorting with exchanges and jumps, respectively. This solves a long-standing open problem by Scharnow, Tinnefeld, and Wegener (J. Math. Model. Algorithm 3(4):349–366, 2005). For the simplest and cheapest mutation operator, swap (swapping adjacent elements), we give a tight runtime bound of $$\Theta (n^2)$$ via a parallel BubbleSort algorithm and a delay sequence argument. This proves that the simplest and cheapest mutation operator is also the fastest for sorting and solving planar OBCM instances.