A characterization of planar graphs by Trémaux orders (Q1065816)

From MaRDI portal
scientific article
Language Label Description Also known as
English
A characterization of planar graphs by Trémaux orders
scientific article

    Statements

    A characterization of planar graphs by Trémaux orders (English)
    0 references
    1985
    0 references
    A Trémaux tree (or Depth-First-Search tree) of a graph G is a rooted spanning tree (T,r) in G (considered also as a semi-lattice with lowest element r) such that every edge outside T is incident with two comparable vertices in T. A characterization theorem of planar graphs based on the concept of Trémaux tree is stated and proved. The theorem can be used as a topological tool to justify planarity testing algorithms involving Depth-First-Search.
    0 references
    Trémaux tree
    0 references
    Depth-First-Search tree
    0 references
    planar graphs
    0 references
    planarity testing
    0 references
    0 references
    0 references

    Identifiers