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).

Duke Authors

Agarwal, Pankaj K.

Cited Authors

Agarwal, PK; Aronov, B; Pach, J; Pollack, R; Sharir, M

Published Date

January 1, 1996

Published In

Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

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

Citation Source

Scopus