Quasi-planar graphs have a linear number of edges

Pankaj K. Agarwal; Boris Aronov; János Pach; Richard Pollack; Micha Sharir

doi:10.1007/bfb0021784

Quasi-planar graphs have a linear number of edges

Pankaj K. Agarwal, Boris Aronov, János Pach, Richard Pollack, Micha Sharir

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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 maximum number of edges of a quasi-planar graph with n vertices is O(n).

Original language	English (US)
Title of host publication	Graph Drawing - Symposium on Graph Drawing, GD 1995, Proceedings
Editors	Franz J. Brandenburg
Publisher	Springer Verlag
Pages	1-7
Number of pages	7
ISBN (Print)	3540607234, 9783540607236
DOIs	https://doi.org/10.1007/bfb0021784
State	Published - 1996
Event	Symposium on Graph Drawing, GD 1995 - Passau, Germany Duration: Sep 20 1995 → Sep 22 1995

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	1027
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	Symposium on Graph Drawing, GD 1995
Country/Territory	Germany
City	Passau
Period	9/20/95 → 9/22/95

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/bfb0021784

Cite this

Agarwal, P. K., Aronov, B., Pach, J., Pollack, R., & Sharir, M. (1996). Quasi-planar graphs have a linear number of edges. In F. J. Brandenburg (Ed.), Graph Drawing - Symposium on Graph Drawing, GD 1995, Proceedings (pp. 1-7). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1027). Springer Verlag. https://doi.org/10.1007/bfb0021784

Quasi-planar graphs have a linear number of edges. / Agarwal, Pankaj K.; Aronov, Boris; Pach, János et al.
Graph Drawing - Symposium on Graph Drawing, GD 1995, Proceedings. ed. / Franz J. Brandenburg. Springer Verlag, 1996. p. 1-7 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1027).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Agarwal, PK, Aronov, B, Pach, J, Pollack, R & Sharir, M 1996, Quasi-planar graphs have a linear number of edges. in FJ Brandenburg (ed.), Graph Drawing - Symposium on Graph Drawing, GD 1995, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1027, Springer Verlag, pp. 1-7, Symposium on Graph Drawing, GD 1995, Passau, Germany, 9/20/95. https://doi.org/10.1007/bfb0021784

Agarwal PK, Aronov B, Pach J, Pollack R, Sharir M. Quasi-planar graphs have a linear number of edges. In Brandenburg FJ, editor, Graph Drawing - Symposium on Graph Drawing, GD 1995, Proceedings. Springer Verlag. 1996. p. 1-7. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/bfb0021784

Agarwal, Pankaj K. ; Aronov, Boris ; Pach, János et al. / Quasi-planar graphs have a linear number of edges. Graph Drawing - Symposium on Graph Drawing, GD 1995, Proceedings. editor / Franz J. Brandenburg. Springer Verlag, 1996. pp. 1-7 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{2a5211bb6e3d4b87bbe126687b81f3a5,

title = "Quasi-planar graphs have a linear number of edges",

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 maximum number of edges of a quasi-planar graph with n vertices is O(n).",

author = "Agarwal, {Pankaj K.} and Boris Aronov and J{\'a}nos Pach and Richard Pollack and Micha Sharir",

year = "1996",

doi = "10.1007/bfb0021784",

language = "English (US)",

isbn = "3540607234",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "1--7",

editor = "Brandenburg, {Franz J.}",

booktitle = "Graph Drawing - Symposium on Graph Drawing, GD 1995, Proceedings",

note = "Symposium on Graph Drawing, GD 1995 ; Conference date: 20-09-1995 Through 22-09-1995",

}

TY - GEN

T1 - Quasi-planar graphs have a linear number of edges

AU - Agarwal, Pankaj K.

AU - Aronov, Boris

AU - Pach, János

AU - Pollack, Richard

AU - Sharir, Micha

PY - 1996

Y1 - 1996

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

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

UR - http://www.scopus.com/inward/record.url?scp=84947903127&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84947903127&partnerID=8YFLogxK

U2 - 10.1007/bfb0021784

DO - 10.1007/bfb0021784

M3 - Conference contribution

AN - SCOPUS:84947903127

SN - 3540607234

SN - 9783540607236

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 1

EP - 7

BT - Graph Drawing - Symposium on Graph Drawing, GD 1995, Proceedings

A2 - Brandenburg, Franz J.

PB - Springer Verlag

T2 - Symposium on Graph Drawing, GD 1995

Y2 - 20 September 1995 through 22 September 1995

ER -

Quasi-planar graphs have a linear number of edges

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this