A topological graph is k-quasi-planar if it does not contain k pairwise crossing edges. A topological graph is simple if every pair of its edges intersect at most once (either at a vertex or at their intersection). In 1996, Pach, Shahrokhi. and Szegedy  showed that every n-vertex simple k-quasi-planar graph contains at most O(n(log n)(2k-4)) edges. This upper bound was recently improved (for large k) by Fox and Pach  to n(log n)(O(log k)). In this note, we show that all such graphs contain at most (n log(2) n)2(alpha ck(n)) edges, where alpha(n) denotes the inverse Ackermann function and c(k) is a constant that depends only on k.
- View record in Web of Science
Record created on 2013-02-27, modified on 2017-03-20