QUASI-PLANAR GRAPHS HAVE A LINEAR NUMBER OF EDGES

Authors
AGARWAL PK ARONOV B PACH J POLLACK R SHARIR M
Citation
Pk. Agarwal et al., QUASI-PLANAR GRAPHS HAVE A LINEAR NUMBER OF EDGES, Combinatorica, 17(1), 1997, pp. 1-9
Citations number
8
Categorie Soggetti
Mathematics, Pure",Mathematics
Journal title
Combinatorica → ACNP
ISSN journal
02099683
Volume
17
Issue
1
Year of publication
1997
Pages
1 - 9
Database
ISI
SICI code
0209-9683(1997)17:1<1:QGHALN>2.0.ZU;2-O
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 max imum number of edges of a quasi-planar graph with n vertices is O(n).