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

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)O(n). Fox and Pach showed that every k-quasi-planar graph with n   vertices has at most n(log⁡n)O(log⁡k)n(log⁡n)O(log⁡k) edges. We improve this upper bound to 2α(n)cnlog⁡n2α(n)cnlog⁡n, where α(n)α(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(nlog⁡n)O(nlog⁡n) edges. This improves the previously known upper bound of 2α(n)cnlog⁡n2α(n)cnlog⁡n obtained by Fox, Pach, and Suk.