On the linearity of testing planarity of graphs (Q1095918)

From MaRDI portal
Revision as of 19:55, 12 July 2023 by Importer (talk | contribs) (‎Created a new Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
On the linearity of testing planarity of graphs
scientific article

    Statements

    On the linearity of testing planarity of graphs (English)
    0 references
    0 references
    1986
    0 references
    In 1978, the author [Acta Math. Appl. Sinica 1, 395-406 (1978)] published a paper in which a characteristic theorem of planarity of a graph was provided as determining if another graph has a fundamental circuit with a certain property. However, the new graph is with, at worst, quadratic order of the vertex number of the original graph. This paper presents a new criterion of testing planarity of a graph based on what the author obtained before. Fortunately, it is equivalent to finding a spanning tree in another graph with only linear order of the vertex number of the original one in the worst case.
    0 references
    testing planarity
    0 references

    Identifiers