On Minimizing Crossings in Storyline Visualizations

Kostitsyna, Irina and Nöllenburg, Martin and Polishchuk, Valentin and Schulz, André and Strash, Darren (2015) On Minimizing Crossings in Storyline Visualizations. In: Graph Drawing and Network Visualization: 23rd International Symposium, GD 2015, September 24-26, 2015, Los Angeles, CA, USA , pp. 192-198 (Official URL: http://dx.doi.org/10.1007/978-3-319-27261-0_16).

Full text not available from this repository.


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(nlogn) crossings. Furthermore, we show that there exist storylines in this restricted case that require Ω(nlogn) 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!^2*klogk+k!^2*m), where m is the number of meetings.

Item Type:Conference Paper
Classifications:G Algorithms and Complexity > G.420 Crossings
P Styles > P.480 Layered
P Styles > P.999 Others
Z Theory > Z.999 Others
ID Code:1488

Repository Staff Only: item control page


Adolphson, D., Hu, T.C.: Optimal linear ordering. SIAM J. Appl. Math. 25(3), 403–423 (1973)

Chung, F.R.K.: A conjectured minimum valuation tree (I. Cahit). SIAM Rev. 20(3), 601–604 (1978)

Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979)

Garey, M.R., Johnson, D.S.: Crossing number is NP-complete. SIAM J. Alg. Disc. Meth. 4(3), 312–316 (1983)

Muelder, C., Crnovrsanin, T., Sallaberry, A., Ma, K.-L.: Egocentric storylines for visual analysis of large dynamic graphs. In: IEEE Big Data’13, pp. 56–62 (2013)

Pach, J., Rubin, N., Tardos, G.: On the Richter-Thomassen conjecture about pairwise intersecting closed curves. In: Discrete Algorithms (SODA’15), pp. 1506–1516 (2015)

Šeĭdvasser, M.A.: The optimal numbering of the vertices of a tree. Diskret. Analiz 17, 56–74 (1970)

Sleator, D.D., Tarjan, R.E.: A data structure for dynamic trees. J. Comput. System Sci. 26(3), 362–391 (1983)

Sugiyama, K., Tagawa, S., Toda, M.: Methods for visual understanding of hierarchical system structures. IEEE Trans. Syst. Man Cybernet. 11(2), 109–125 (1981)

Tanahashi, Y., Ma, K.-L.: Design considerations for optimizing storyline visualizations. IEEE Trans. Vis. Comput. Graph. 18(12), 2679–2688 (2012)