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

Drawing Graphs with Low Visual Complexity

以较低的视觉复杂度绘制图表

基本信息

批准号：
256873462
负责人：
Professor Dr. André Schulz
金额：
--
依托单位：
Lehrgebiet Theoretische Informatik
依托单位国家：
德国
项目类别：
Research Grants
财政年份：
2014
资助国家：
德国
起止时间：
2013-12-31 至 2017-12-31
项目状态：
已结题

来源：
https://gepris.dfg.de/gepris/projekt/256873462?language=en
关键词：
Drawing Graphs Low Visual Complexity

项目摘要

In this project we study a novel design criterion for drawings of planar graphs. A common goal in graph drawing is to create visualizations that can be easily captured by the viewer. This includes, that the drawings of the edges and the vertices are well-distinguishable. From a classical point of view the realizations of the edges and vertices form the ground set of geometric objects, whose combination defines the drawing. In this project we investigate how one can construct drawings assembled from a very small ground set. The crucial point in our idea is that a simple path in the graph can be realized as a single object of the ground set. In this sense, we can obtain a drawing that uses fewer objects than it has edges. The drawing is therefore an arrangement of simple geometric objects, whose skeleton gives the input graph. We refer to the size of the ground set as the visual complexity of the drawing. As geometric objects we consider straight-line segments and circular arcs. We focus on drawings of planar graphs and study as subclasses trees, series-parallel graphs, outerplanar graphs, planar 3-trees and triangulations.We plan to develop algorithms for generating drawings with low visual complexity. The constructed drawings should also fulfill other well-established design criteria. In order to evaluate the quality of the constructed drawings we also study the worst-case visual complexity for planar graphs with respect to the number of edges. From this question we can derive a number of interesting combinatorial question in the area of graph theory, which we would like to investigate in this project. We claim that drawings with low visual complexity are esthetically appealing. We plan to verify our claim by empirical user studies. Moreover, we want to test if drawings with low visual complexity have other desirable properties. Finally, we would like to study the relationship between contact representations of circular arcs and drawings of graphs with low visual complexity.

在这个项目中，我们研究了一种新的平面图的设计准则。图形绘制中的一个共同目标是创建可以容易地被查看器捕获的可视化。这包括，边和顶点的绘图是很好区分的。从经典的角度来看，边和顶点的实现形成了几何对象的基础集，其组合定义了绘图。在这个项目中，我们将研究如何从一个非常小的地面集合组装图纸。在我们的想法中的关键点是，图中的一个简单的路径可以实现为一个单一的对象的基集。从这个意义上说，我们可以得到一幅使用的对象比它的边缘少的图。因此，绘图是简单几何对象的排列，其骨架给出输入图形。我们将地面的大小称为绘图的视觉复杂度。作为几何对象，我们考虑直线段和圆弧。我们主要研究平面图的绘图，并将其作为树、串-平行图、外平面图、平面3-树和三角剖分的子类进行研究，并计划开发低视觉复杂度的绘图算法。施工图还应满足其他完善的设计标准。为了评估质量的构造图纸，我们还研究了最坏情况下的视觉复杂度平面图的边的数量。从这个问题中，我们可以得到一些有趣的组合问题，在该地区的图论，我们想在这个项目中进行调查。我们认为，低视觉复杂度的绘画在美学上具有吸引力。我们计划通过实证用户研究来验证我们的说法。此外，我们想测试低视觉复杂度的绘图是否具有其他理想的属性。最后，我们想研究圆弧的接触表示和低视觉复杂度的图形绘制之间的关系。