Minimizing Wiggles in Storyline Visualizations

Abstract

A storyline visualization is a two-dimensional drawing of a special kind of time-varying hypergraph H(t), where the x-axis represents time and the vertices (also called characters) are x-monotone curves. At each point in time t, the vertices form a permutation such that groups of adjacent characters in H(t) occupy consecutive vertical positions to indicate a meeting at time t, see Fig.1. Each character can only be part of at most one meeting at each point in time. This kind of visualization has been introduced for illustrating movie narratives [8], but is also more generally used in information visualization [6, 11]. Several aesthetic optimization criteria have been proposed [6, 11], including minimization of crossing, line wiggles, and white-space gaps. While crossing minimization has been studied from an algorithmic point of view in recent years [4, 5, 7], minimizing line wiggles, as another important quality criterion, which is similar to bend minimization in node-link diagrams [9, 10], has not been investigated on its own. We note that the problem of minimizing corners or moves in permutation diagrams [2, 3] is related to wiggle minimization, yet does not include the temporal aspects of storylines with meetings over time and their induced character ordering constraints. We present the first integer linear pro- gramming (ILP) model for exact wiggle minimization in storyline visualizations without an initial permutation. We can include crossing minimization into a weighted multicriteria ILP model and show examples of a first case study.