权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Algorithms for Interaction in Graph Drawing

绘图中的交互算法

基本信息

批准号：
244429338
负责人：
Professorin Dr. Dorothea Wagner
金额：
--
依托单位：
Institut für Theoretische Informatik (ITI)
依托单位国家：
德国
项目类别：
Research Grants
财政年份：
2014
资助国家：
德国
起止时间：
2013-12-31 至 2018-12-31
项目状态：
已结题

来源：
https://gepris.dfg.de/gepris/projekt/244429338?language=en
关键词：
Algorithms Interaction 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.

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