@article{Suk:184706,
title = {k-Quasi-Planar Graphs},
author = {Suk, Andrew},
publisher = {Springer-Verlag Berlin},
journal = {Graph Drawing},
address = {Berlin},
volume = {7034},
series = {Lecture Notes in Computer Science},
pages = {12. 266-277},
year = {2012},
abstract = {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 [16] 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 [8] 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.},
url = {http://infoscience.epfl.ch/record/184706},
}