Algorithms for Interaction in Graph Drawing

• Applicant: Professorin Dr. Dorothea Wagner
• Subject Area: Theoretical Computer Science
• Term: from 2014 to 2019
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 244429338

In the past decades the computer was a tool expected to merely ``get the job done''. With the development of technology, computers are considered more as an assistant collaborating with the user to reach his goal. In graph drawing, this new understanding shifts the focus from fully automatic layout algorithms towards more interactive workflows, where drawings are produced by iterative interaction between the user and the system.In this project we propose to investigate methods to interactively manipulate graph layouts. At present, there is a huge gap in the level of expressiveness of the existing interaction techniques. Basic operations such as individual node movement and simple manual operations like rotation or scaling provide strongcontrol but are not suitable for large layout changes. On the other hand, constrained graph drawing algorithms allow automatic creation of layouts subject to (possibly interactively specified) constraints onthe final drawing. This approach allows substantial layout changes and, given an efficient algorithm, scales well to large graphs. However, it provides a limited control over the layout process, unless a large amount of constraints is specified. We seek to shrink the gap between these extremes. On the one hand we will develop new constrained layout algorithms, which allow the user to specify positions for a subset of vertices or the curve complexity of important edges. On the other hand we propose to increase the expressiveness of the manual interaction methods by introducing higher-level primitive operations, which are easy-to-use, and yet are powerful enough to allow the user to perform substantial layout modifications with only few interactionsteps. This is achieved by designing algorithms that support the user in the manipulation of graphs by continuously updating the layout in response to the user input. To enhance the usefulness of these operations and make them applicable also to large graphs, we will study methods to create suitably small abstractions of such graphs, which can be used for the interaction. To compute the final layout of the original graph, we will design techniques to consistently extrapolate changes that are performed on the abstraction.

• DFG Programme: Research Grants