TY - CONF
AB - Bundling crossings is a strategy which can enhance the readability of graph drawings. In this paper we consider bundlings for families of pseudosegments, i.e., simple curves such that any two have share at most one point at which they cross. Our main result is that there is a polynomial-time algorithm to compute an 8-approximation of the bundled crossing number of such instances (up to adding a term depending on the facial structure). This 8-approximation also holds for bundlings of good drawings of graphs. In the special case of circular drawings the approximation factor is 8 (no extra term), this improves upon the 10-approximation of Fink et al. [6]. We also show how to compute a 92-approximation when the intersection graph of the pseudosegments is bipartite.
AU - Arroyo Guevara, Alan M
AU - Felsner, Stefan
ID - 11185
SN - 0302-9743
T2 - WALCOM 2022: Algorithms and Computation
TI - Approximating the bundled crossing number
VL - 13174
ER -