Quasi-planar graphs have a linear number of edges (Q1375051)

A graph is quasi-planar if it can be drawn in the plane with no three pairwise crossing edges. It is shown that a quasi-planar graph on \(n\) vertices may contain at most \(O(n)\) edges. This improves an earlier \(O(n{\log}^2n)\) given by \textit{J. Pach}, \textit{F. Sharokhi} and \textit{M. Szegedy} [Applications of the crossing number, Proc. 10th Annual ACM Symp. on Computational Geometry, 198-202 (1994)]. A more general problem is also considered, namely what is the maximum number of edges of a graph on \(n\) vertices which can be drawn in the plane with no \(k\) pairwise crossing edges, for some constant \(k\geq 3\). Combining the main result of this paper with the analysis given in the paper of J. Pach at al. mentioned above, a more general result is obtained, i.e. a graph on \(n\) vertices which can be drawn in the plane with no \(k\) pairwise crossing edges contains at most \(O(n{\log}^{2k-6}n)\) edges. Several interesting problems are posed.