Geodesic
Approximating the Bundled Crossing Number
Journal of Graph Algorithms and Applications, Special Issue on Parameterized and Approximation Algorithms in Graph Drawing , Tome 27 (2023) no. 6, pp. 433-457.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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.
DOI : 10.7155/jgaa.00629
Keywords: graph drawing, crossings, bundling, approximation algorithm, FPT algorithm, greedy algorithm, circular drawing, bipartite instances 
@article{JGAA_2023_27_6_a2,
     author = {Alan Arroyo and Stefan Felsner},
     title = {Approximating the {Bundled} {Crossing} {Number}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {433--457},
     publisher = {mathdoc},
     volume = {27},
     number = {6},
     year = {2023},
     doi = {10.7155/jgaa.00629},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00629/}
}
TY  - JOUR
AU  - Alan Arroyo
AU  - Stefan Felsner
TI  - Approximating the Bundled Crossing Number
JO  - Journal of Graph Algorithms and Applications
PY  - 2023
SP  - 433
EP  - 457
VL  - 27
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00629/
DO  - 10.7155/jgaa.00629
LA  - en
ID  - JGAA_2023_27_6_a2
ER  - 
%0 Journal Article
%A Alan Arroyo
%A Stefan Felsner
%T Approximating the Bundled Crossing Number
%J Journal of Graph Algorithms and Applications
%D 2023
%P 433-457
%V 27
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00629/
%R 10.7155/jgaa.00629
%G en
%F JGAA_2023_27_6_a2
Alan Arroyo; Stefan Felsner. Approximating the Bundled Crossing Number. Journal of Graph Algorithms and Applications, 
							Special Issue on Parameterized and Approximation Algorithms in Graph Drawing
					, Tome 27 (2023) no. 6, pp. 433-457. doi : 10.7155/jgaa.00629. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00629/

Cité par Sources :