论文标题
饱和$ k $ - 平面图很少
Saturated $k$-Plane Drawings with Few Edges
论文作者
论文摘要
如果没有边缘超过$ k $倍的边缘，则图的图是$ k $平面。在本文中，我们研究了几个边缘的饱和$ K $平面图。这是$ k $ - 平面图，其中无需违反$ k $ - planarity而无法添加边缘。对于每个数量的顶点$ n> k+1 $，我们提供了一个紧密的结构，其中$ \ frac {n-1} {k+1} $边缘对于边缘可以自行切换的情况。如果我们将图纸限制为$ \ ell $ -simple，我们表明饱和$ K $ - 平面图中的边数必须更高。我们介绍了几乎没有边缘的构造，不同的值是$ k $和$ \ ell $。最后，我们研究了饱和的直线$ k $平面图。
A drawing of a graph is $k$-plane if no edge is crossed more than $k$ times. In this paper we study saturated $k$-plane drawings with few edges. This are $k$-plane drawings in which no edge can be added without violating $k$-planarity. For every number of vertices $n>k+1$, we present a tight construction with $\frac{n-1}{k+1}$ edges for the case in which the edges can self-intersect. If we restrict the drawings to be $\ell$-simple we show that the number of edges in saturated $k$-plane drawings must be higher. We present constructions with few edges for different values of $k$ and $\ell$. Finally, we investigate saturated straight-line $k$-plane drawings.
