Drawing Graphs: Geometric Aspects Beyond Planarity

点击翻译按钮获取中文摘要

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?