Block Crossings in Storyline Visualizations

DOI10.1007/978-3-319-50106-2_30zbMATH Open1478.68266arXiv1609.00321OpenAlexW2962908739MaRDI QIDQ2961533FDOQ2961533

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)

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.

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

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

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)

Cites Work

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

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)