Two-Layer Drawings with a Tree on Top: Vertex Splits and Fixed-Parameter Algorithms
2026-07-27 • Computational Geometry
Computational GeometryData Structures and Algorithms
AI summaryⓘ
The authors study a way to draw bipartite graphs with two rows of points connected by lines, aiming to completely remove line crossings by splitting some points into copies. They focus on a version where the order of points in one row must follow a given tree structure, inspired by anatomical data visualization. They develop efficient algorithms that work well when the number of splits or the tree complexity is small and improve on past methods for the simpler version without order constraints. They also test their approach and find it practical for real cases.
bipartite graphtwo-layer drawingvertex splittingedge crossingNP-hardparameterized complexityfixed-parameter algorithmETH (Exponential Time Hypothesis)graph visualizationalgorithm implementation
Authors
Alexander Firbas, Robert Ganian, Sylvain Meunier, Martin Nöllenburg
Abstract
Two-layer drawings of bipartite graphs place the vertices of each part on one of two parallel lines and draw the edges as straight-line links. Traditionally, the optimization goal is to find vertex permutations on one or both layers that minimize the induced number of edge crossings. This problem is NP-hard, and crossing-minimal solutions may still contain many crossings. Recently, there has been growing interest in an orthogonal optimization goal, namely removing all crossings by vertex splitting, i.e., replacing original vertices by two or more copies and distributing the adjacencies among them. In this paper, we study a natural extension of the two-layer vertex splitting problem in which the vertex order on one layer is constrained by a given auxiliary tree $T$, motivated by applications such as the visualization of anatomical hierarchies in the Human Reference Atlas. We investigate the parameterized complexity of this problem and obtain two main contributions: (1) a fixed-parameter algorithm with respect to the number $k$ of splits, and (2) an ETH-tight single-exponential fixed-parameter algorithm with respect to the maximum degree of $T$. Moreover, we build on the latter result to obtain an ETH-tight single-exponential algorithm for the classical unconstrained version of the problem, improving upon the previous $O^*(2^{k\cdot \log k})$ algorithms. Finally, we also implement our algorithm and show that it performs well in practice.