TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 26.01.2017


Page Content

to Navigation

Block Crossings in Storyline Visualizations

Armin Danziger (TU Berlin)


Storyline visualizations help to visualize encounters of 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
curves corresponding to the characters participating in the meeting run close together for the time of the
meeting. In order to keep the visual complexity low, rather than just minimizing pairwise crossings of
curves, Dijk et al. [GD ’16] propose to minimize the number of block crossings, where a block crossing
is a crossing of two blocks each consisting of locally parallel curves. In this talk, I present the following
selected results from the paper. Minimizing the number of block crossings is NP-hard. Furthermore, the
problem is FPT with respect to the number of characters. Finally, if the meetings are of bounded size,
the problem admits a constant-factor approximation.


Armin Danziger
TEL 512

Back to the research colloquium site.


Quick Access

Schnellnavigation zur Seite über Nummerneingabe