New bounds on the maximum number of edges in k-quasi-planar graphs

الأصل · EN

A topological graph is k-quasi-planar if it does not contain k pairwise crossing edges. A 20-year-old conjecture asserts that for every fixed k, the maximum number of edges in a k-quasi-planar graph on n vertices is O(n). Fox and Pach showed that every k-quasi-planar graph with n vertices has at most n(n)O(k) edges. We improve this upper bound to 2α⁽ⁿ⁾ᶜn n, where α(n) denotes the inverse Ackermann function and c depends only on k, for k-quasi-planar graphs in which any two edges intersect in a bounded number of points. We also show that every k-quasi-planar graph with n vertices in which any two edges have at most one point in common has at most O(n n) edges. This improves the previously known upper bound of 2α⁽ⁿ⁾ᶜn n obtained by Fox, Pach, and Suk.