Drawing Graphs with 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.