Algorithms for Interaction in Graph Drawing

在过去的几十年里，计算机被认为只是一种“完成工作”的工具。随着技术的发展，计算机被更多地视为一个助手，与用户合作，以达到他的目标。在图形绘制中，这种新的理解将焦点从全自动布局算法转移到更具交互性的工作流程，其中图形是由用户和系统之间的迭代交互产生的。在这个项目中，我们建议研究交互操作图形布局的方法。目前，现有的交互技术在表达水平上存在着巨大的差距。基本操作（如单个节点移动）和简单的手动操作（如旋转或缩放）提供了强大的控制，但不适合大规模布局更改。另一方面，受约束的图形绘制算法允许在最终绘制的约束（可能是交互指定的）下自动创建布局。这种方法允许大量的布局变化，并且在给定有效算法的情况下，可以很好地扩展到大型图形。然而，除非指定了大量的约束，否则它对布局过程提供了有限的控制。我们力求缩小这两个极端之间的差距。一方面，我们将开发新的约束布局算法，允许用户指定顶点子集的位置或重要边的曲线复杂度。另一方面，我们建议通过引入更高级的原语操作来增加手动交互方法的表现力，这些操作易于使用，并且足够强大，允许用户只需要几个交互步骤就可以执行大量的布局修改。这是通过设计算法来实现的，该算法通过响应用户输入不断更新布局来支持用户对图形的操作。为了增强这些操作的有用性，并使它们也适用于大型图，我们将研究创建此类图的适当小抽象的方法，这些抽象可用于交互。为了计算原始图形的最终布局，我们将设计一些技术来一致地推断在抽象上执行的更改。

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.