liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
On Minimizing Crossings in Storyline Visualizations
TU Eindhoven, Netherlands.
TU Wien, Austria.
Linköping University, Department of Science and Technology, Communications and Transport Systems. Linköping University, Faculty of Science & Engineering.
Fernuniv, Germany.
Show others and affiliations
2015 (English)In: GRAPH DRAWING AND NETWORK VISUALIZATION, GD 2015, SPRINGER INT PUBLISHING AG , 2015, Vol. 9411, 192-198 p.Conference paper (Refereed)Text
Abstract [en]

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 fixedparameter tractable, when parameterized on the number of characters k. Our algorithm runs in time O(k!(2) k log k+ k!(2) m), where m is the number of meetings.

Place, publisher, year, edition, pages
SPRINGER INT PUBLISHING AG , 2015. Vol. 9411, 192-198 p.
Lecture Notes in Computer Science, ISSN 0302-9743
National Category
Civil Engineering
URN: urn:nbn:se:liu:diva-127596DOI: 10.1007/978-3-319-27261-0_16ISI: 000373628600016ISBN: 978-3-319-27261-0; 978-3-319-27260-3OAI: diva2:925939
23rd International Symposium on Graph Drawing and Network Visualization (GD)
Available from: 2016-05-03 Created: 2016-05-03 Last updated: 2016-05-03

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Polishchuk, Valentin
By organisation
Communications and Transport SystemsFaculty of Science & Engineering
Civil Engineering

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 20 hits
ReferencesLink to record
Permanent link

Direct link