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?n 2 ? ( n ) c n log ? 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 ( n log ? n ) edges. This improves the previously known upper bound of 2?(n)cnlog?n 2 ? ( n ) c n log ? n obtained by Fox, Pach, and Suk.
k-quasi-planar graphs topological graphs turn-type problems