Drawing Graphs: Geometric Aspects Beyond Planarity

在这个项目中，我们想要研究低视觉复杂性的图形绘制。我们所说的视觉复杂性指的是表示图形所需的几何基元的数量；例如，坡度、线段或圆弧、直线或圆，以及在三维空间中的平面或球体。同时，我们希望通过寻找在平面上“驯服”交叉点的方法，或者通过将当前的研究扩展到3-空间，来关注最近的“超越平面性”方向图的几何方面。例如，考虑线段数，这是其并集包含给定图的直线图的最小线段数。这种对图形视觉复杂性的度量已经在平面图中得到了相当广泛的研究。但是1-平面图，即可以画出每条边至多可以与另一条边相交的图，又如何呢？如果我们知道这样的图形实际上有一条至多有一条交叉边的直线图形，我们能不能非平凡地限制这样一幅图形所需的线段数量？我们能在3-空间中得到更好的界吗？我们最近介绍的平面覆盖数也是一个很好的例子：每个平面图在平面上都有一个相交自由线。然而，如果我们离开平面图的现实，我们需要多少个平面才能适应给定图的无交叉直线绘制？考虑几乎平面图，即去除单边后变成平面图的图。虽然交叉最小化即使对于几乎平面图也是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?