A graph is called quasi-planar if it can be drawn in the plane so that no three of its edges are pairwise crossing. It is shown that the maximum number of edges of a quasi-planar graph with n vertices is O(n).
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Computational Mathematics