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(log k)) 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 logn obtained by Fox, Pach, and Suk.
展开▼
