Block Crossings in Storyline Visualizations

DOI10.1007/978-3-319-50106-2_30MaRDI QIDQ2961533zbMATH OpenOpenAlexFDO

Authors Thomas C. van Dijk, Martin Fink, Norbert Fischer, Fabian Lipp, Peter Markfelder, Alexander Wolff, Oleksandr Ravs'kyj, Subhash Suri

Publication date 21 February 2017

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1609.00321

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Nonnumerical algorithms (68W05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Mathematics and literature (00A64)

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. 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. Our main results are as follows. We show that minimizing the number of block crossings is NP-hard, and we develop, for meetings of bounded size, a constant-factor approximation. We also present two fixed-parameter algorithms and, for meetings of size 2, a greedy heuristic that we evaluate experimentally.

Recommendations

• Block crossings in storyline visualizations
• Computing storyline visualizations with few block crossings
• Crossing Minimization in Storyline Visualization
• On minimizing crossings in storyline visualizations
• Storyline visualizations with ubiquitous actors
• Crossings in grid drawings
• Crossing patterns of segments
• Crossing Layout in Non-planar Graph Drawings

Cites work

• Block crossings in storyline visualizations
• Characterization problems for graphs, partially ordered sets, lattices, and families of sets
• Depth-first iterative-deepening: An optimal admissible tree search
• Interval hypergraphs and D-interval hypergraphs
• On minimizing crossings in storyline visualizations
• On planar supports for hypergraphs
• Ordering metro lines by block crossings
• Sorting a bridge hand

Cited in

(5)

• On minimizing crossings in storyline visualizations
• Computing storyline visualizations with few block crossings
• Storyline visualizations with ubiquitous actors
• Crossing Minimization in Storyline Visualization
• Block crossings in storyline visualizations

This page was built for publication: Block Crossings in Storyline Visualizations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2961533)