Drawing Graphs: Geometric Aspects Beyond Planarity

在这个项目中，我们想研究绘制具有低视觉复杂性的图形。所谓视觉复杂性，我们指的是表示图形所需的几何原语的数量；例如，斜坡、线段或圆弧、直线或圆，以及在三维空间中的平面或球体。与此同时，我们希望通过寻找“驯服”平面交叉的方法或将当前的研究扩展到三维空间，来关注最近“超越平面”方向图像绘制的几何方面。例如，考虑线段数，它是其并集包含给定图的直线绘制的线段的最小数量。这种图形视觉复杂性的测量方法已经在平面图形中得到了广泛的研究。但是对于一维图呢，也就是那些每条边最多只能与另一条边相交的图呢？如果我们知道这样的图实际上是一条直线，每条边最多有一个交叉点，我们是否可以非平凡地限制我们需要的线段的数量？我们能否在三维空间中得到更好的边界，在那里交叉不是什么大问题？我们最近介绍的平面覆盖数也可以作为演示示例：每个平面图在平面上都有一个交叉的自由直线绘图。然而，如果我们离开了平面图形的领域，我们需要多少个平面来容纳一个给定图形的无交叉直线？准平面图，即去掉一条边后变成平面的图。即使对于几乎是平面的图，交叉最小化也是np困难的，我们知道我们可以在四个平面的并集上绘制任何几乎是平面的图（或者，简单地说，两个球体）。在这个领域有许多令人兴奋的开放性问题。例如，次线性的平面数是否足以满足三次图？

In this project we want to investigate drawing graphs with lowvisual complexity. By visual complexity we mean the number ofgeometric primitives needed to represent the graph; for example,slopes, line segments or circular arcs, lines or circles, and, in3-space, planes or spheres. At the same time, we want to focus ongeometric aspects of the recent "beyond planarity" direction ingraph drawing by either finding ways to "tame" crossings in theplane or by extending the current research to 3-space.Consider, for example, the segment number, which is the minimum numberof line segments whose union contains a straight-line drawing of a givengraph. This measurement for the visual complexity of a graph hasalready been studied quite extensively for planar graphs. But whatabout 1-planar graphs, that is, graphs that can be drawn such thateach edge can cross at most one other edge? If we know that such agraph actually has a straight-line drawing with at most one crossingper edge, can we non-trivially bound the number of line segments thatwe need for such a drawing? Can we get better bounds in 3-space,where crossings are not much of an issue?The plane cover number that we introduced recently serves as ashowcase example, too: every planar graph has a crossing-freestraight-line drawing in the plane. If we leave, however, the realmof planar graphs, how many planes do we need to accommodate acrossing-free straight-line drawing of a given graph? Consideralmost-planar graphs, that is, graphs that becomes planar after theremoval of a single edge. While crossing minimization is NP-hard evenfor almost-planar graphs, we know that we can draw any almost-planar graph on the union of four planes (or, trivially, two spheres). There are many excitingopen questions in this area. For example, does a sublinear number ofplanes suffice for cubic graphs?