PACE Solver Description: LUNCH - Linear Uncrossing Heuristics

Abstract

The 2024 PACE challenge is on One-Sided Crossing Minimization: Given a bipartite graph with one fixed and one free layer, compute an ordering of the vertices in the free layer that minimizes the number of edge crossings in a straight-line drawing of the graph. Here, we briefly describe our exact, parameterized, and heuristic submissions. The main contribution is an efficient reduction to a weighted version of Directed Feedback Arc Set, allowing us to detect subproblems that can be solved independently.