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 , pp. 1-7(Official URL: http://dx.doi.org/10.1007/BFb0021784).

Full text not available from this repository.

Abstract

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
URI: http://gdea.informatik.uni-koeln.de/id/eprint/42

Actions (login required)

View Item View Item