Quasi-planar graphs have a linear number of edges

Journal Article

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, 1997

Published In

Volume / Issue

  • 17 / 1

Start / End Page

  • 1 - 9

International Standard Serial Number (ISSN)

  • 0209-9683

Digital Object Identifier (DOI)

  • 10.1007/BF01196127

Citation Source

  • Scopus