Veröffentlichung

Titel:

On Minimizing Crossings in Storyline Visualizations

AutorInnen:

Irina Kostitsyna
Martin Nöllenburg
Valentin Polishchuk
André Schulz
Darren Strash

Kategorie:

Konferenzbandbeiträge

erschienen in:

Graph Drawing and Network Visualization - 23rd International Symposium, GD 2015, Los Angeles, CA, USA, September 24-26, 2015, Revised Selected Papers, pp. 192-198

Abstract:

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 Ω(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!²k log k + k!²m), where m is the number of meetings.

Download:

Springer

BibTeX-Eintrag:

@inproceedings{KNPSS15, author = {Irina Kostitsyna and Martin N{\"{o}}llenburg and Valentin Polishchuk and Andr{\'{e}} Schulz and Darren Strash}, editor = {Emilio Di Giacomo and Anna Lubiw}, title = {On Minimizing Crossings in Storyline Visualizations}, booktitle = {Graph Drawing and Network Visualization - 23rd International Symposium, {GD} 2015, Los Angeles, CA, USA, September 24-26, 2015, Revised Selected Papers}, series = {Lecture Notes in Computer Science}, volume = {9411}, pages = {192--198}, publisher = {Springer}, year = {2015}, url = {http://dx.doi.org/10.1007/978-3-319-27261-0_16}, doi = {10.1007/978-3-319-27261-0_16} }