Geodesic
Bundled Crossings Revisited
Journal of Graph Algorithms and Applications, Special issue on Selected papers from the Twenty-seventh International Symposium on Graph Drawing and Network Visualization, GD 2019 , Tome 24 (2020) no. 4, pp. 621-655.

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

An effective way to reduce clutter in a graph drawing that has (many) crossings is to group edges that travel in parallel into bundles. Each edge can participate in many such bundles. Any crossing in this bundled graph occurs between two bundles, i.e., as a bundled crossing. We consider the problem of bundled crossing minimization: A graph is given and the goal is to find a bundled drawing with at most $k$ bundled crossings. We show that the problem is NP-hard when we require a simple drawing. Our main result is an FPT algorithm (in $k$) for simple circular layouts where vertices must be placed on a circle and edges must be drawn inside the circle. These results make use of the connection between bundled crossings and graph genus. We also consider bundling crossings in a given drawing, in particular for storyline visualizations.
DOI : 10.7155/jgaa.00535
Keywords: bundled crossings, circular layout, NP-hard, fixed-parameter tractable, storyline visualization, extended monadic second order logic 
@article{JGAA_2020_24_4_a4,
     author = {Steven Chaplick and Thomas van Dijk and Myroslav Kryven and Ji-won Park and Alexander Ravsky and Alexander Wolff},
     title = {Bundled {Crossings} {Revisited}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {621--655},
     publisher = {mathdoc},
     volume = {24},
     number = {4},
     year = {2020},
     doi = {10.7155/jgaa.00535},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00535/}
}
TY  - JOUR
AU  - Steven Chaplick
AU  - Thomas van Dijk
AU  - Myroslav Kryven
AU  - Ji-won Park
AU  - Alexander Ravsky
AU  - Alexander Wolff
TI  - Bundled Crossings Revisited
JO  - Journal of Graph Algorithms and Applications
PY  - 2020
SP  - 621
EP  - 655
VL  - 24
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00535/
DO  - 10.7155/jgaa.00535
LA  - en
ID  - JGAA_2020_24_4_a4
ER  - 
%0 Journal Article
%A Steven Chaplick
%A Thomas van Dijk
%A Myroslav Kryven
%A Ji-won Park
%A Alexander Ravsky
%A Alexander Wolff
%T Bundled Crossings Revisited
%J Journal of Graph Algorithms and Applications
%D 2020
%P 621-655
%V 24
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00535/
%R 10.7155/jgaa.00535
%G en
%F JGAA_2020_24_4_a4
Steven Chaplick; Thomas van Dijk; Myroslav Kryven; Ji-won Park; Alexander Ravsky; Alexander Wolff. Bundled Crossings Revisited. Journal of Graph Algorithms and Applications, 
							Special issue on Selected papers from the Twenty-seventh International Symposium on Graph Drawing and Network Visualization, GD 2019
					, Tome 24 (2020) no. 4, pp. 621-655. doi : 10.7155/jgaa.00535. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00535/

Cité par Sources :