ThRaSH Seminars Series, Spring 2024

When? On Mondays at 14:00 CEST (12:00 UTC), starting from May 13 and ending on June 24; however, no talk on May 20

Where? Here is a permanent zoom link.

Mailing list? Subscribe to the seminar mailing list here. If you want to get all the ThRaSH-related news, subscribe to this list as well.

Organizers: Benjamin Doerr and Carsten Witt.

Schedule

Abstracts of the talks

13 May 2024

Evolutionary Computation Meets Graph Drawing: Runtime Analysis for Crossing Minimisation on Layered Graph Drawings — Dirk Sudholt, University of Passau, Germany

Graph Drawing aims to make graphs visually comprehensible while faithfully representing their structure. In layered drawings, each vertex is drawn on a horizontal line and edges are drawn as y-monotone curves. A key ingredient for constructing such drawings is the One-Sided Bipartite Crossing Minimization (OBCM) problem: given two layers of a bipartite graph and a fixed horizontal order of 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 the simplest and cheapest mutation operator, swap, shows excellent performance on instances that can be drawn crossing-free, which correspond to a generalised sorting problem. We give a tight runtime bound of Θ(n2) via a parallel BubbleSort algorithm and a delay sequence argument. This gives a positive answer to an open problem from Scharnow, Tinnefeld, and Wegener (2004) on whether the best known bound of O(n2 log n) for sorting in permutation spaces can be improved to Θ(n2), albeit for an even simpler operator.