Suk, Andrew (2012) k-Quasi-Planar Graphs. In: Graph Drawing 19th International Symposium, GD 2011, September 21-23, 2011, Eindhoven, The Netherlands , pp. 266-277 (Official URL: http://dx.doi.org/10.1007/978-3-642-25878-7_26).
Full text not available from this repository.
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)hoch 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(log2n)2α ck(n) edges, where α(n) denotes the inverse Ackermann function and ck is a constant that depends only on k.
Repository Staff Only: item control page