 |
| Home | Issues | About JGAA | Instructions for Authors |
|
Special issue on Selected papers from the Twenty-fourth International Symposium on Graph Drawing and Network Visualization, GD 2016
DOI: 10.7155/jgaa.00443
Block Crossings in Storyline Visualizations
Thomas C. van Dijk,
Martin Fink,
Norbert Fischer,
Fabian Lipp,
Peter Markfelder,
Alexander Ravsky,
Subhash Suri, and
Alexander Wolff
Vol. 21, no. 5, pp. 873-913, 2017. Regular paper.
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.
|
Submitted: December 2016.
Reviewed: March 2017.
Revised: May 2017.
Reviewed: June 2017.
Revised: July 2017.
Accepted: August 2017.
Final: August 2017.
Published: October 2017.
|
Journal publisher
|
Journal network
|
Journal Supporters
|
