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.

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. We consider a fundamental problem from this domain, the One-Sided Bipartite Crossing Minimisation (OBCM) problem. Given a bipartite graph with two layers and a fixed horizontal order of vertices on the first layer, the objective is to order the vertices on the second layer to minimise the number of edge crossings.

Evolutionary algorithms (EAs) are universal solvers inspired by principles of natural evolution. In many applications, EAs produce astonishingly good solutions. To complement recent theoretical advances in the analysis of EAs on graph drawing [Baumann et al., 2024], we contribute a fundamental empirical study. We consider the so-called One-Sided Bipartite Crossing Minimisation (OBCM): 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 empirically analyse the performance of simple EAs for OBCM and compare different mutation operators on the underlying permutation ordering problem: exchanging two elements (exchange), swapping adjacent elements (swap) and jumping an element to a new position (jump). EAs using jumps easily outperform all deterministic algorithms in terms of solution quality after a reasonable number of generations. We also design variations of the best-performing EAs to reduce the execution time for each generation. The improved EAs can obtain the same solution quality as before and run up to 100 times faster.

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 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.

Motivated by the planarization of 2-layered straight-line drawings, we consider the problem of modifying a graph such that the resulting graph has pathwidth at most 1. The problem Pathwidth-One Vertex Explosion (POVE) asks whether such a graph can be obtained using at most 𝑘 vertex explosions, where a vertex explosion replaces a vertex 𝑣 by deg(𝑣) degree-1 vertices, each incident to exactly one edge that was originally incident to 𝑣. For POVE, we give an FPT algorithm with running time 𝑂(4𝑘 ⋅ 𝑚) and an 𝑂(𝑘2) kernel, thereby improving over the 𝑂(𝑘6) kernel by Ahmed et al. [2] in a more general setting. Similarly, a vertex split replaces a vertex 𝑣 by two distinct vertices 𝑣1 and 𝑣2 and distributes the edges originally incident to 𝑣 arbitrarily to 𝑣1 and 𝑣2. Analogously to POVE, we define the problem variant Pathwidth-One Vertex Splitting (POVS) that uses the split operation instead of vertex explosions. Here we obtain a linear kernel and an algorithm with running time 𝑂((6𝑘 + 12)𝑘 ⋅ 𝑚). This answers an open question by Ahmed et al. [2]. Finally, we consider the problem Π-VertexSplitting (Π-VS), which generalizes the problem POVS and asks whether a given graph can be turned into a graph of a specific graph class Π using at most 𝑘 vertex splits. For graph classes Π that can be dfined in monadic second-order graph logic (MSO2), we show that the problem Π-VS can be expressed as an MSO2 formula, resulting in an FPT algorithm for Π-VS parameterized by 𝑘 if Π additionally has bounded treewidth. We obtain the same result for the problem variant using vertex explosions. [2] R. Ahmed, S.G. Kobourov, M. Kryven, An FPT algorithm for bipartite vertex splitting, in: P. Angelini, R. von Hanxleden (Eds.), Graph Drawing and Network Visualization -30th International Symposium, GD 2022, in: Lecture Notes in Computer Science, vol.13764, Springer, 2022, pp.261--268.