Journal of Graph Algorithms and Applications

Special Issue on Parameterized and Approximation Algorithms in Graph Drawing

Approximating the Bundled Crossing Number

Alan Arroyo and Stefan Felsner

Vol. 27, no. 6, pp. 433-457, 2023. Regular paper.

Abstract Bundling crossings is a strategy which can enhance the readability of graph drawings. In this paper we consider good drawings, i.e., we require that any two edges have at most one common point which can be a common vertex or a crossing. Our main result is that there is a polynomial-time algorithm to compute an 8-approximation of the bundled crossing number of a good drawing with no toothed hole. In general the number of toothed holes has to be added to the 8-approximation. In the special case of circular drawings the approximation factor is 8, this improves upon the 10-approximation of Fink et al.[Fink et al., LATIN 2016]. Our approach also works with the same approximation factor for families of pseudosegments, i.e., curves intersecting at most once. We also show how to compute a $\frac{9}{2}$-approximation when the intersection graph of the pseudosegments is bipartite and has no toothed hole.