A characterization of planar graphs by Trémaux orders (Q1065816)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3922679
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | A characterization of planar graphs by Trémaux orders |
scientific article; zbMATH DE number 3922679 |
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.9099071621894836
0 references
0.9049963355064392
0 references
0.8391952514648438
0 references
0.7451169490814209
0 references
