On minimizing crossings in storyline visualizations

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

doi:10.1007/978-3-319-27261-0_16

On minimizing crossings in storyline visualizations

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

21 Citations (Scopus)

227 Downloads (Pure)

Abstract

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 language	English
Title of host publication	Proc. 23rd International Symposium Graph Drawing and Network Visualization (GD)
Editors	E. Di Giacomo , A. Lubiw
Place of Publication	Dordrecht
Publisher	Springer
Pages	192-198
Number of pages	7
ISBN (Electronic)	978-3-319-27261-0
ISBN (Print)	978-3-319-27260-3
DOIs	https://doi.org/10.1007/978-3-319-27261-0_16
Publication status	Published - 2015
Event	23rd International Symposium on Graph Drawing and Network Visualization (GD 2015) - California State University Northridge, Los Angeles, United States Duration: 24 Sept 2015 → 26 Sept 2015 Conference number: 23 http://www.csun.edu/gd2015/

Publication series

Name	Lecture Notes in Computer Science
Volume	9411
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	23rd International Symposium on Graph Drawing and Network Visualization (GD 2015)
Abbreviated title	GD 2015
Country/Territory	United States
City	Los Angeles
Period	24/09/15 → 26/09/15
Internet address	http://www.csun.edu/gd2015/

Access to Document

10.1007/978-3-319-27261-0_16

final_submittedFinal author version , 295 KB

Cite this

Kostitsyna, I., Nöllenburg, M., Polishchuk, V., Schulz, A., & Strash, D. (2015). On minimizing crossings in storyline visualizations. In E. Di Giacomo , & A. Lubiw (Eds.), Proc. 23rd International Symposium Graph Drawing and Network Visualization (GD) (pp. 192-198). (Lecture Notes in Computer Science; Vol. 9411). Springer. https://doi.org/10.1007/978-3-319-27261-0_16

@inproceedings{032bec4e1a9140eaaf887746a1d4417f,

title = "On minimizing crossings in storyline visualizations",

abstract = "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.",

author = "I. Kostitsyna and M. N{\"o}llenburg and V. Polishchuk and A. Schulz and D. Strash",

year = "2015",

doi = "10.1007/978-3-319-27261-0\_16",

language = "English",

isbn = "978-3-319-27260-3",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "192--198",

editor = "\{Di Giacomo \}, E. and A. Lubiw",

booktitle = "Proc. 23rd International Symposium Graph Drawing and Network Visualization (GD)",

address = "Germany",

note = "23rd International Symposium on Graph Drawing and Network Visualization (GD 2015), GD 2015 ; Conference date: 24-09-2015 Through 26-09-2015",

url = "http://www.csun.edu/gd2015/",

}

Kostitsyna, I, Nöllenburg, M, Polishchuk, V, Schulz, A & Strash, D 2015, On minimizing crossings in storyline visualizations. in E Di Giacomo & A Lubiw (eds), Proc. 23rd International Symposium Graph Drawing and Network Visualization (GD). Lecture Notes in Computer Science, vol. 9411, Springer, Dordrecht, pp. 192-198, 23rd International Symposium on Graph Drawing and Network Visualization (GD 2015), Los Angeles, California, United States, 24/09/15. https://doi.org/10.1007/978-3-319-27261-0_16

On minimizing crossings in storyline visualizations. / Kostitsyna, I.; Nöllenburg, M.; Polishchuk, V. et al.
Proc. 23rd International Symposium Graph Drawing and Network Visualization (GD). ed. / E. Di Giacomo ; A. Lubiw. Dordrecht: Springer, 2015. p. 192-198 (Lecture Notes in Computer Science; Vol. 9411).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - On minimizing crossings in storyline visualizations

AU - Kostitsyna, I.

AU - Nöllenburg, M.

AU - Polishchuk, V.

AU - Schulz, A.

AU - Strash, D.

N1 - Conference code: 23

PY - 2015

Y1 - 2015

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-319-27261-0_16

DO - 10.1007/978-3-319-27261-0_16

M3 - Conference contribution

AN - SCOPUS:84952046512

SN - 978-3-319-27260-3

T3 - Lecture Notes in Computer Science

SP - 192

EP - 198

BT - Proc. 23rd International Symposium Graph Drawing and Network Visualization (GD)

A2 - Di Giacomo , E.

A2 - Lubiw, A.

PB - Springer

CY - Dordrecht

T2 - 23rd International Symposium on Graph Drawing and Network Visualization (GD 2015)

Y2 - 24 September 2015 through 26 September 2015

ER -

On minimizing crossings in storyline visualizations

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this