On the maximum number of edges in quasi-planar graphs (Q878960)

The paper improves on the known result that graphs which can be properly drawn in the plane so that there are no three pairwise crossing edges (quasiplanar graphs) have a linear number of edges in relation to the number of vertices by proving that such a graph has no more than \(8| V| -20\) edges for \(| V| \geq 3\). The authors show that for each positive integer \(n\) there is a quasiplanar graph with \(| V| =n\) and \(7n-O(1)\) edges. They also give an exceedingly simple and gemlike proof of the linearity of the number of edges, and consider some relaxations and restrictions of quasiplanarity for which they are able to close the gap between the upper bounds and the lower bounds given by construction.