标题： 关于5-平面图密度的初步观察 显示英文标题

标题： A first view on the density of 5-planar graphs

摘要： $k$-平面图是平面图的推广，可以在平面上绘制，每条边最多有 $k > 0$ 次交叉。 $k$-平面性研究中的核心问题之一是最大边密度，即一个具有 $n$ 个顶点的 $k$-平面图可能具有的边的最大数量。 对于 $k\leq 2$类的广义 $k$- 平面图已有大量结果，但由于这些类别的复杂性，关于增加 $k=3$或 $4$的结果却很少。 我们通过探索 $5$- 平面图类，朝更大的 $k>4$迈出了第一步。 尽管我们的主要工具仍然是放电技术，但对更密集部分结构的更好理解以一种更简单的方式得出了相应的密度界限。 我们首先将技术的一个简化版本应用于外$5$-平面图，并利用由此得到的密度界断言，当$k$很小时，最大密度$5$-平面图的结构不同于均匀结构。 作为本文的核心结果，我们随后证明了简单$5$-平面图最多有$\frac{340}{49}(n-2) \approx 6.94(n-2)$条边，这比之前最好的界$\approx8.3n$有了极大的改进。 这甚至意味着交叉引理 $cr(G) \ge c \frac{m^3}{n^2}$ 中的首项常数从 $c=\frac{1}{27.48}$ 略微改进为 $c=\frac{1}{27.19}$。 为了展示新技术的潜力，我们还将其应用于其他图类，例如 4 平面图和 6 平面图。 显示英文摘要

摘要： $k$-planar graphs are generalizations of planar graphs that can be drawn in the plane with at most $k > 0$ crossings per edge. One of the central research questions of $k$-planarity is the maximum edge density, i.e., the maximum number of edges a $k$-planar graph on $n$ vertices may have. While there are numerous results for the classes of general $k$-planar graphs for $k\leq 2$, there are only very few results for increasing $k=3$ or $4$ due to the complexity of the classes. We make a first step towards even larger $k>4$ by exploring the class of $5$-planar graphs. While our main tool is still the discharging technique, a better understanding of the structure of the denser parts leads to corresponding density bounds in a much simpler way. We first apply a simplified version of our technique to outer $5$-planar graphs and use the resulting density bound to assert that the structure of maximally dense $5$-planar graphs differs from the uniform structure when $k$ is small. As the central result of this paper, we then show that simple $5$-planar graphs have at most $\frac{340}{49}(n-2) \approx 6.94(n-2)$ edges, which is a drastic improvement from the previous best bound of $\approx8.3n$. This even implies a small improvement of the leading constant in the Crossing Lemma $cr(G) \ge c \frac{m^3}{n^2}$ from $c=\frac{1}{27.48}$ to $c=\frac{1}{27.19}$. To demonstrate the potential of our new technique, we also apply it to other graph classes, such as 4-planar and 6-planar graphs.