Quasi-Planar Graphs Have a Linear Number of Edges
Agarwal, Pankaj K. and Aronov, Boris and Pach, János and Pollack, Richard and Sharir, Micha (1996) Quasi-Planar Graphs Have a Linear Number of Edges. In: Symposium on Graph Drawing, GD 1995, September 20-22, 1995, Passau, Germany , pp. 1-7 (Official URL: http://dx.doi.org/10.1007/BFb0021784).
Full text not available from this repository.
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).
Repository Staff Only: item control page