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 proceedingConference contribution


    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 languageEnglish (US)
    Title of host publicationGraph Drawing - Symposium on Graph Drawing, GD 1995, Proceedings
    EditorsFranz J. Brandenburg
    PublisherSpringer Verlag
    Number of pages7
    ISBN (Print)3540607234, 9783540607236
    StatePublished - 1996
    EventSymposium on Graph Drawing, GD 1995 - Passau, Germany
    Duration: Sep 20 1995Sep 22 1995

    Publication series

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


    OtherSymposium on Graph Drawing, GD 1995

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Computer Science(all)

    Fingerprint Dive into the research topics of 'Quasi-planar graphs have a linear number of edges'. Together they form a unique fingerprint.

    Cite this