
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.
Computational Geometry (cs.CG), FOS: Computer and information sciences, Discrete Mathematics (cs.DM), \(\frac{9}{2}\)-approximation, Graph algorithms (graph-theoretic aspects), Graph representations (geometric and intersection representations, etc.), Computer Science - Computational Geometry, bundling crossings, Computer Science - Discrete Mathematics
Computational Geometry (cs.CG), FOS: Computer and information sciences, Discrete Mathematics (cs.DM), \(\frac{9}{2}\)-approximation, Graph algorithms (graph-theoretic aspects), Graph representations (geometric and intersection representations, etc.), Computer Science - Computational Geometry, bundling crossings, Computer Science - Discrete Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
