Quasi-planar graphs have a linear number of edges
Published
Conference Paper
© Springer-Verlag Berlin Heidelberg 1996. 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).
Full Text
Duke Authors
Cited Authors
- Agarwal, PK; Aronov, B; Pach, J; Pollack, R; Sharir, M
Published Date
- January 1, 1996
Published In
Volume / Issue
- 1027 /
Start / End Page
- 1 - 7
Electronic International Standard Serial Number (EISSN)
- 1611-3349
International Standard Serial Number (ISSN)
- 0302-9743
International Standard Book Number 10 (ISBN-10)
- 3540607234
International Standard Book Number 13 (ISBN-13)
- 9783540607236
Digital Object Identifier (DOI)
- 10.1007/bfb0021784
Citation Source
- Scopus