Geodesic
Block Crossings in Storyline Visualizations
Journal of Graph Algorithms and Applications, Special issue on Selected papers from the Twenty-fourth International Symposium on Graph Drawing and Network Visualization, GD 2016 , Tome 21 (2017) no. 5, pp. 873-913.

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

Storyline visualizations help visualize encounters of the characters in a story over time. Each character is represented by an x-monotone curve that goes from left to right visualizing progression of time. A meeting is represented by having the characters that participate in the meeting run close together for some time. In order to keep the visual complexity low, rather than just minimizing pairwise crossings of curves, we propose to count block crossings, that is, pairs of intersecting bundles of lines. In a block crossing, two blocks of parallel lines intersect each other, which is less distracting than the same number of individual crossings being spread over the drawing. In this paper, we show that minimizing the number of block crossings is NP-hard, even if all meetings are of size 2. For this special case, we present a greedy heuristic, which we evaluate experimentally. We show that the general case is fixed-parameter tractable. Our main results is a constant-factor approximation algorithm for meetings of bounded size. The algorithm is based on (approximately) solving a hyperedge deletion problem on hypergraphs that may be of independent interest. 
@article{JGAA_2017_21_5_a4,
     author = {Thomas van Dijk and Martin Fink and Norbert Fischer and Fabian Lipp and Peter Markfelder and Alexander Ravsky and Subhash Suri and Alexander Wolff},
     title = {Block {Crossings} in {Storyline} {Visualizations}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {873--913},
     publisher = {mathdoc},
     volume = {21},
     number = {5},
     year = {2017},
     doi = {10.7155/jgaa.00443},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00443/}
}
TY  - JOUR
AU  - Thomas van Dijk
AU  - Martin Fink
AU  - Norbert Fischer
AU  - Fabian Lipp
AU  - Peter Markfelder
AU  - Alexander Ravsky
AU  - Subhash Suri
AU  - Alexander Wolff
TI  - Block Crossings in Storyline Visualizations
JO  - Journal of Graph Algorithms and Applications
PY  - 2017
SP  - 873
EP  - 913
VL  - 21
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00443/
DO  - 10.7155/jgaa.00443
LA  - en
ID  - JGAA_2017_21_5_a4
ER  - 
%0 Journal Article
%A Thomas van Dijk
%A Martin Fink
%A Norbert Fischer
%A Fabian Lipp
%A Peter Markfelder
%A Alexander Ravsky
%A Subhash Suri
%A Alexander Wolff
%T Block Crossings in Storyline Visualizations
%J Journal of Graph Algorithms and Applications
%D 2017
%P 873-913
%V 21
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00443/
%R 10.7155/jgaa.00443
%G en
%F JGAA_2017_21_5_a4
Thomas van Dijk; Martin Fink; Norbert Fischer; Fabian Lipp; Peter Markfelder; Alexander Ravsky; Subhash Suri; Alexander Wolff. Block Crossings in Storyline Visualizations. Journal of Graph Algorithms and Applications, 
							Special issue on Selected papers from the Twenty-fourth International Symposium on Graph Drawing and Network Visualization, GD 2016
					, Tome 21 (2017) no. 5, pp. 873-913. doi : 10.7155/jgaa.00443. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00443/

Cité par Sources :