# On minimizing crossings in storyline visualizations

I. Kostitsyna, M. Nöllenburg, V. Polishchuk, A. Schulz, D. Strash

## Samenvatting

In a storyline visualization, we visualize a collection of interacting characters (e.g., in a movie, play, etc.) by \$x\$-monotone curves that converge for each interaction, and diverge otherwise. Given a storyline with \$n\$ characters, we show tight lower and upper bounds on the number of crossings required in any storyline visualization for a restricted case. In particular, we show that if (1) each meeting consists of exactly two characters and (2) the meetings can be modeled as a tree, then we can always find a storyline visualization with \$O(n\log n)\$ crossings. Furthermore, we show that there exist storylines in this restricted case that require \$\Omega(n\log n)\$ crossings. Lastly, we show that, in the general case, minimizing the number of crossings in a storyline visualization is fixed-parameter tractable, when parameterized on the number of characters \$k\$. Our algorithm runs in time \$O(k!^2k\log k + k!^2m)\$, where \$m\$ is the number of meetings.
Originele taal-2 Engels s.n. Gepubliceerd - 2015

### Publicatie series

Naam arXiv 1509.00442