Quasi-planar graphs have a linear number of edges


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