Tight Runtime Bounds for Evolutionary Algorithms on Sorting and Crossing Minimisation for Layered Graph Drawings
Open Access
- 23 May 2026
- journal article
- research article
- Published by Springer Nature in Algorithmica
- Vol. 88 (3) , 49
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.
Keywords
Funding Information
- Universität Passau
This publication has 37 references indexed in Scilit:
- Evolutionary Algorithms for Cardinality-Constrained Ising Models2022
- 2-Layer k-Planar Graphs2020
- Theory of Evolutionary Computation2020
- Probabilistic Tools for the Analysis of Randomized Optimization Heuristics2019
- Analyzing Evolutionary Algorithms2013
- Ranking and Drawing in Subexponential Time2011
- Exact Solutions to the Traveling Salesperson Problem by a Population-Based Evolutionary Algorithm2009
- A Parallel Approach to Row-Based VLSI Layout Using Stochastic Hill-Climbing2003
- One Sided Crossing Minimization Is NP-Hard for Sparse Graphs2002
- The Delay Sequence Argument2001