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.
%0 Journal Article
%1 dfflmrsw-bcsv-JGAA17
%A van Dijk, Thomas C.
%A Fink, Martin
%A Fischer, Norbert
%A Lipp, Fabian
%A Markfelder, Peter
%A Ravsky, Alexander
%A Suri, Subhash
%A Wolff, Alexander
%D 2017
%J Journal of Graph Algorithms & Applications
%K myown
%N 5
%P 873--913
%R 10.7155/jgaa.00443
%T Block Crossings in Storyline Visualizations
%V 21
%X 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{dfflmrsw-bcsv-JGAA17,
abstract = {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.},
added-at = {2022-05-17T09:43:08.000+0200},
author = {van Dijk, Thomas C. and Fink, Martin and Fischer, Norbert and Lipp, Fabian and Markfelder, Peter and Ravsky, Alexander and Suri, Subhash and Wolff, Alexander},
biburl = {https://www.bibsonomy.org/bibtex/25211465a5688cb436cc0bb7febf878a5/nfischer},
doi = {10.7155/jgaa.00443},
interhash = {4d023b68d93096ae4853bdcf89c0e50b},
intrahash = {5211465a5688cb436cc0bb7febf878a5},
journal = {Journal of Graph Algorithms \& Applications},
keywords = {myown},
note = {Conference version received \textbf{best paper award} (track A) at GD'16.},
number = 5,
pages = {873--913},
timestamp = {2022-05-17T09:43:08.000+0200},
title = {Block Crossings in Storyline Visualizations},
volume = 21,
year = 2017
}