The Number of Edges in k-Quasi-planar Graphs
The Number of Edges in k-Quasi-planar Graphs
复制标题
k-拟平面图中的边数
DOI：
--
复制
发表时间：
2011
影响因子：
0.8
通讯作者：
Andrew Suk
中科院分区：
文献类型：
--
作者：
J. Fox;J. Pach;Andrew Suk
一个平面图称为k$-拟平面图，如果它不包含k$两交叉边。长期以来，人们证明了对于任意固定的k，n阶k-拟平面图的最大边数为O（n）。最好的上界是$n（log n）^{O（log k）}$。在本文中，我们在图的每对边至多相交一次的特殊情况下，将这个界改进为$（nlog n）2^{alpha（n）^{c_k}}$。这里$alpha（n）$表示阿克曼函数的逆（增长非常缓慢）。我们还进一步的猜想k$-拟平面图，其中每一个边缘是$x$-单调曲线画。推广了Valtr的一些思想，证明了这类图的最大边数至多为2 ^{ck^6}nlog n$.
A graph drawn in the plane is called $k$-quasi-planar if it does not contain $k$ pairwise crossing edges. It has been conjectured for a long time that for every fixed $k$, the maximum number of edges of a $k$-quasi-planar graph with $n$ vertices is $O(n)$. The best known upper bound is $n(log n)^{O(log k)}$. In the present paper, we improve this bound to $(nlog n )2^{alpha(n)^{c_k}}$ in the special case where the graph is drawn in such a way that every pair of edges meet at most once. Here $alpha(n)$ denotes the (extremely slowly growing) inverse of the Ackermann function. We also make further progress on the conjecture for $k$-quasi-planar graphs in which every edge is drawn as an $x$-monotone curve. Extending some ideas of Valtr, we prove that the maximum number of edges of such graphs is at most $2^{ck^6}nlog n$.