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

12 Citations (Scopus)
136 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 Sept 201526 Sept 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
Country/TerritoryUnited States
CityLos Angeles
Internet address


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

Cite this