On minimizing crossings in storyline visualizations

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

8 Citations (Scopus)
45 Downloads (Pure)


In a storyline visualization, we visualize a collection of inter- acting 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. Fur- thermore, 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 (Formula presented.), where m is the number of meetings.

Original languageEnglish
Title of host publicationProc. 23rd International Symposium Graph Drawing and Network Visualization (GD)
EditorsE. Di Giacomo , A. Lubiw
Place of PublicationDordrecht
Number of pages7
ISBN (Electronic)978-3-319-27261-0
ISBN (Print)978-3-319-27260-3
Publication statusPublished - 2015
Event23rd International Symposium on Graph Drawing and Network Visualization (GD 2015) - California State University Northridge, Los Angeles, United States
Duration: 24 Sep 201526 Sep 2015
Conference number: 23

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference23rd International Symposium on Graph Drawing and Network Visualization (GD 2015)
Abbreviated titleGD 2015
CountryUnited States
CityLos Angeles
Internet address

Fingerprint Dive into the research topics of 'On minimizing crossings in storyline visualizations'. Together they form a unique fingerprint.

Cite this