Top

Published in:

2016 | OriginalPaper | Chapter

Crossing Minimization in Storyline Visualization

Authors : Martin Gronemann, Michael Jünger, Frauke Liers, Francesco Mambelli

Published in: Graph Drawing and Network Visualization

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

A storyline visualization is a layout that represents the temporal dynamics of social interactions along time by the convergence of chronological lines. Among the criteria oriented at improving aesthetics and legibility of a representation of this type, a small number of line crossings is the hardest to achieve. We model the crossing minimization in the storyline visualization problem as a multi-layer crossing minimization problem with tree constraints. Our algorithm can compute a layout with the minimum number of crossings of the chronological lines. Computational results demonstrate that it can solve instances with more than 100 interactions and with more than 100 chronological lines to optimality.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter A Note on the Practicality of Maximal Planar Subgraph Algorithms

next chapter Block Crossings in Storyline Visualizations

Angelini, P., Da Lozzo, G., Di Battista, G., Frati, F., Roselli, V.: The importance of being proper: (in clustered-level planarity and \(T\)-level planarity). Theoret. Comput. Sci. 571, 1–9 (2015)MathSciNetCrossRefMATH

Barahona, F., Jünger, M., Reinelt, G.: Experiments in quadratic 0–1 programming. Math. Program. 44, 127–137 (1989)MathSciNetCrossRefMATH

Barahona, F., Mahjoub, A.R.: On the cut polytope. Math. Program. 36(2), 157–173 (1986)MathSciNetCrossRefMATH

Baumann, F., Buchheim, C., Liers, F.: Exact bipartite crossing minimization under tree constraints. In: Festa, P. (ed.) SEA 2010. LNCS, vol. 6049, pp. 118–128. Springer, Heidelberg (2010). doi:10.1007/978-3-642-13193-6_11 CrossRef

Bekos, M.A., Kaufmann, M., Potika, K., Symvonis, A.: Line crossing minimization on metro maps. In: Hong, S.-H., Nishizeki, T., Quan, W. (eds.) GD 2007. LNCS, vol. 4875, pp. 231–242. Springer, Heidelberg (2008). doi:10.1007/978-3-540-77537-9_24 CrossRef

Buchheim, C., Wiegele, A., Zheng, L.: Exact algorithms for the quadratic linear ordering problem. INFORMS J. Comput. 22(1), 168–177 (2010)MathSciNetCrossRefMATH

Buchin, K., Buchin, M., Byrka, J., Nöllenburg, M., Okamoto, Y., Silveira, R.I., Wolff, A.: Drawing (Complete) binary tanglegrams. Algorithmica 62(1), 309–332 (2012)MathSciNetCrossRefMATH

Chimani, M., Hungerländer, P., Jünger, M., Mutzel, P.: An SDP approach to multi-level crossing minimization. In: Müller-Hannemann, M., Werneck, R. (eds.) Proceedings of the 13th Workshop on Algorithm Engineering and Experiments, ALENEX 2011, pp. 116–126. Society for Industrial and Applied Mathematics (2011)

Cui, W., Liu, S., Tan, L., Shi, C., Song, Y., Gao, Z.J., Tong, X., Qu, H.: TextFlow: towards better understanding of evolving topics in text. IEEE Trans. Vis. Comput. Graph. 17(12), 2412–2421 (2011)CrossRef

10.

De Simone, C.: The cut polytope and the Boolean quadric polytope. Discrete Math. 79(1), 71–75 (1990)MathSciNetCrossRefMATH

11.

Fernau, H., Kaufmann, M., Poths, M.: Comparing trees via crossing minimization. J. Comput. Syst. Sci. 76(7), 593–608 (2010)MathSciNetCrossRefMATH

12.

Fink, M., Pupyrev, S.: Metro-line crossing minimization: hardness, approximations, and tractable cases. In: Wismath, S., Wolff, A. (eds.) GD 2013. LNCS, vol. 8242, pp. 328–339. Springer, Heidelberg (2013). doi:10.1007/978-3-319-03841-4_29 CrossRef

13.

Garey, M.R., Johnson, D.S.: Crossing number is NP-complete. SIAM J. Algebr. Discrete Methods 4(3), 312–316 (1983)MathSciNetCrossRefMATH

14.

Grötschel, M., Jünger, M., Reinelt, G.: Facets of the linear ordering polytope. Math. Program. 33(1), 43–60 (1985)MathSciNetCrossRefMATH

15.

Hammer, P.: Some network flow problems solved with pseudo-Boolean programming. Oper. Res. 13, 388–399 (1965)MathSciNetCrossRef

16.

Healy, P., Kuusik, A.: Algorithms for multi-level graph planarity testing and layout. Theoret. Comput. Sci. 320(2–3), 331–344 (2004)MathSciNetCrossRefMATH

17.

IBM: IBM ILOG CPLEX Optimization Studio 12.6 (2014). http://www-01.ibm.com/software/commerce/optimization/cplex-optimizer/

18.

Jünger, M., Lee, E.K., Mutzel, P., Odenthal, T.: A polyhedral approach to the multi-layer crossing minimization problem. In: Di Battista, G. (ed.) GD 1997. LNCS, vol. 1353, pp. 13–24. Springer, Heidelberg (1997). doi:10.1007/3-540-63938-1_46 CrossRef

19.

Jünger, M., Leipert, S., Mutzel, P.: Level planarity testing in linear time. In: Whitesides, S.H. (ed.) GD 1998. LNCS, vol. 1547, pp. 224–237. Springer, Heidelberg (1998). doi:10.1007/3-540-37623-2_17 CrossRef

20.

Jünger, M., Thienel, S.: The ABACUS system for branch-and-cut-and-price algorithms in integer programming and combinatorial optimization. Softw. Pract. Exp. 30, 1325–1352 (2000)CrossRefMATH

21.

Knuth, D.E.: The Stanford GraphBase source (1993). ftp://ftp.cs.stanford.edu/pub/sgb/sgb.tar.gz

22.

Kostitsyna, I., Nöllenburg, M., Polishchuk, V., Schulz, A., Strash, D.: On minimizing crossings in storyline visualizations. In: Di Giacomo, E., Lubiw, A. (eds.) GD 2015. LNCS, vol. 9411, pp. 192–198. Springer, Heidelberg (2015). doi:10.1007/978-3-319-27261-0_16 CrossRef

23.

Liers, F., Jünger, M., Reinelt, G., Rinaldi, G.: Computing exact ground states of hard ising spin glass problems by branch-and-cut. In: Hartmann, A.K., Rieger, H. (eds.) New Optimization Algorithms in Physics, pp. 47–69. Wiley-VCH, Weinheim (2004)

24.

Liu, S., Wu, Y., Wei, E., Liu, M., Liu, Y.: StoryFlow: tracking the evolution of stories. IEEE Trans. Vis. Comput. Graph. 19(12), 2436–2445 (2013)CrossRef

25.

Muelder, C.W., Crnovrsanin, T., Sallaberry, A., Ma, K.L.: Egocentric storylines for visual analysis of large dynamic graphs. In: Proceedings of the 2013 IEEE International Conference on Big Data, pp. 56–62 (2013)

26.

Munroe, R.: xkcd #657: Movie Narrative Charts (2009). http://xkcd.com/657/

27.

Nöllenburg, M., Völker, M., Wolff, A., Holten, D.: Drawing binary tanglegrams: an experimental evaluation. In: Finocchi, I., Hershberger, J. (eds.) Proceedings of the 11th Workshop on Algorithm Engineering and Experiments, ALENEX 2009, pp. 106–119. Society for Industrial and Applied Mathematics (2009)

28.

Ogawa, M., Ma, K.L.: Software evolution storylines. In: Telea, A.C. (ed.) Proceedings of the 5th International Symposium on Software Visualization, SOFTVIS 2010, pp. 35–42. ACM (2010)

29.

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

30.

Tanahashi, Y.: Movie data set (2013). http://vis.cs.ucdavis.edu/~tanahashi/data_downloads/storyline_visualizations/story_data.tar

31.

Tanahashi, Y., Hsueh, C.H., Ma, K.L.: An efficient framework for generating storyline visualizations from streaming data. IEEE Trans. Vis. Comput. Graph. 21(6), 730–742 (2015)CrossRef

32.

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

33.

Vehlow, C., Beck, F., Auwärter, P., Weiskopf, D.: Visualizing the evolution of communities in dynamic graphs. Comput. Graph. Forum 34(1), 277–288 (2015)CrossRef

34.

Wotzlaw, A., Speckenmeyer, E., Porschen, S.: Generalized \(k\)-ary tanglegrams on level graphs: a satisfiability-based approach and its evaluation. Discrete Appl. Math. 160(16–17), 2349–2363 (2012)MathSciNetCrossRefMATH

35.

Zimmer, K.: Ein Branch-and-Cut-Algorithmus für Mehrschichten-Kreuzungsmini-mierung. Master’s thesis, Institut für Informatik, Universität zu Köln (2013)

Title: Crossing Minimization in Storyline Visualization
Authors: Martin Gronemann
Michael Jünger
Frauke Liers
Francesco Mambelli
Publisher: Springer International Publishing
Book: Graph Drawing and Network Visualization
Print ISBN: 978-3-319-50105-5

Electronic ISBN: 978-3-319-50106-2

Copyright Year: 2016
DOI: https://doi.org/10.1007/978-3-319-50106-2_29

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner