EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

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

Jakob Baumann, Ignaz Rutter, Dirk Sudholt

Algorithmica · 2026-06 · 88 (3)

DOI: 10.1007/s00453-025-01361-5 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Algorithmica, online erschienen am 23.05.2026. Verfasst von Jakob Baumann und 2 weiteren Autor:innen. Die Arbeit nennt 43 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Universität Passau.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Förderung

  • Universität Passau

Zitieren

APA

Baumann, J., Rutter, I., & Sudholt, D. (2026). Tight Runtime Bounds for Evolutionary Algorithms on Sorting and Crossing Minimisation for Layered Graph Drawings. Algorithmica, 88(3). https://doi.org/10.1007/s00453-025-01361-5

Vancouver

Baumann J, Rutter I, Sudholt D. Tight Runtime Bounds for Evolutionary Algorithms on Sorting and Crossing Minimisation for Layered Graph Drawings. Algorithmica. 2026;88(3). doi:10.1007/s00453-025-01361-5

BibTeX
@article{Baumann2026,
  author = {Baumann, Jakob and Rutter, Ignaz and Sudholt, Dirk},
  title = {Tight Runtime Bounds for Evolutionary Algorithms on Sorting and Crossing Minimisation for Layered Graph Drawings},
  journal = {Algorithmica},
  year = {2026},
  volume = {88},
  number = {3},
  doi = {10.1007/s00453-025-01361-5}
}
Kostenlos starten →