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).

Item Type:Conference Paper
Additional Information:10.1007/BFb0021784
Classifications:Z Theory > Z.750 Topology
G Algorithms and Complexity > G.420 Crossings
ID Code:42

Repository Staff Only: item control page


M. Golumbic, Algorithmic Graph Theory, Academic Press, New York, 1980.

A. Gyárfás, On the chromatic number of multiple interval graphs and overlap graphs, Discrete Math. 55 (1985), 161-166.

A. Gyárfás and J. Lehel, Covering and coloring problems for relatives of intervals, Discrete Math. 55 (1985), 167-180.

A. V. Kostochka, On upper bounds for the chomatic number of graphs, in: Modeli i metody optimizacii, Tom 10, Akademiya Nauk SSSR, Sibirskoe Otdelenie, 1988, 204-226.

J. Pach and P. K. Agarwal, Combinatorial Geometry, Wiley-Interscience, New York, 1995.

J. Pach, F. Sharokhi and M. Szegedy, Applications of crossing number, Proc. 10th Annual ACM Symp. on Computational Geometry (1994), pp. 198-202. Also to appear in Algorithmica.