Evolutionary Computation Meets Graph Drawing: Runtime Analysis for Crossing Minimisation on Layered Graph Drawings
Jakob Baumann, Ignaz Rutter, Dirk Sudholt · Proceedings of the Genetic and Evolutionary Computation Conference · 2024
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.