×

Block crossings in storyline visualizations. (English) Zbl 1478.68266

Hu, Yifan (ed.) et al., Graph drawing and network visualization. 24th international symposium, GD 2016, Athens, Greece, September 19–21, 2016. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 9801, 382-398 (2016).
Summary: Storyline visualizations help visualize encounters of the characters in a story over time. Each character is represented by an \(x\)-monotone curve that goes from left to right. A meeting is represented by having the characters that participate in the meeting run close together for some time. In order to keep the visual complexity low, rather than just minimizing pairwise crossings of curves, we propose to count block crossings, that is, pairs of intersecting bundles of lines.
Our main results are as follows. We show that minimizing the number of block crossings is NP-hard, and we develop, for meetings of bounded size, a constant-factor approximation. We also present two fixed-parameter algorithms and, for meetings of size 2, a greedy heuristic that we evaluate experimentally.
For the entire collection see [Zbl 1352.68012].

MSC:

68R10 Graph theory (including graph drawing) in computer science
00A64 Mathematics and literature
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68W05 Nonnumerical algorithms
68W25 Approximation algorithms
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Buchin, K., van Kreveld, M.J., Meijer, H., Speckmann, B., Verbeek, K.: On planar supports for hypergraphs. J. Graph Algorithms Appl. 15(4), 533–549 (2011) · Zbl 1276.05081 · doi:10.7155/jgaa.00237
[2] Bulteau, L., Fertin, G., Rusu, I.: Sorting by transpositions is difficult. SIAM J. Discrete Math. 26(3), 1148–1180 (2012) · Zbl 1256.05004 · doi:10.1137/110851390
[3] van Dijk, T.C., Fink, M., Fischer, N., Lipp, F., Markfelder, P., Ravsky, A., Suri, S., Wolff, A.: Block crossings in storyline visualizations (2016). http://arxiv.org/abs/1609.00321 · Zbl 1372.05222
[4] Eriksson, H., Eriksson, K., Karlander, J., Svensson, L., Wästlund, J.: Sorting a bridge hand. Discrete Math. 241(1), 289–300 (2001) · Zbl 0990.05145 · doi:10.1016/S0012-365X(01)00150-9
[5] Fink, M., Pupyrev, S., Wolff, A.: Ordering metro lines by block crossings. J. Graph Algorithms Appl. 19(1), 111–153 (2015) · Zbl 1307.05212 · doi:10.7155/jgaa.00351
[6] Kim, N.W., Card, S.K., Heer, J.: Tracing genealogical data with timenets. In: Proceedings of the International Conference Advanced Visual Interfaces (AVI 2010), pp. 241–248 (2010) · doi:10.1145/1842993.1843035
[7] Korf, R.E.: Depth-first iterative-deepening: an optimal admissible tree search. Artif. Intell. 27(1), 97–109 (1985) · Zbl 0573.68030 · doi:10.1016/0004-3702(85)90084-0
[8] 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 · Zbl 1471.68200 · doi:10.1007/978-3-319-27261-0_16
[9] Moore, J.I.: Interval hypergraphs and \[ D \] -interval hypergraphs. Discrete Math. 17(2), 173–179 (1977) · Zbl 0357.05073 · doi:10.1016/0012-365X(77)90148-0
[10] Muelder, C., Crnovrsanin, T., Sallaberry, A., Ma, K.: Egocentric storylines for visual analysis of large dynamic graphs. In: Proceedings of the IEEE International Conference Big Data, pp. 56–62 (2013) · doi:10.1109/BigData.2013.6691715
[11] Munroe, R.: Movie narrative charts. https://xkcd.com/657/
[12] Tanahashi, Y., Ma, K.: Design considerations for optimizing storyline visualizations. IEEE Trans. Vis. Comput. Graph. 18(12), 2679–2688 (2012) · doi:10.1109/TVCG.2012.212
[13] Trotter, W.T., Moore, J.I.: Characterization problems for graphs, partially ordered sets, lattices, and families of sets. Discrete Math. 16(4), 361–381 (1976) · Zbl 0356.06007 · doi:10.1016/S0012-365X(76)80011-8
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.