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. An old conjecture states 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 and no pair of edges intersecting in more than O(1) points has at most n(log n)O(logk) edges. We improve this upper bound to 2α(n)c n log n, where α(n) denotes the inverse Ackermann function, and c depends only on k. We also show that every k-quasi-planar graph with n vertices and every two edges have at most one point in common has at most O(n log n) edges. This improves the previously known upper bound of 2α(n)c n log n obtained by Fox, Pach, and Suk. © 2013 Springer International Publishing Switzerland.