Quasi-planar graphs have a linear number of edges

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

    Research output: Contribution to journalArticlepeer-review

    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 languageEnglish (US)
    Pages (from-to)1-9
    Number of pages9
    JournalCombinatorica
    Volume17
    Issue number1
    DOIs
    StatePublished - 1997

    ASJC Scopus subject areas

    • Discrete Mathematics and Combinatorics
    • Computational Mathematics

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

    Cite this