A characterization of planar graphs by Trémaux orders (Q1065816): Difference between revisions
From MaRDI portal
Changed an Item |
Set OpenAlex properties. |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Efficient Planarity Testing / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5677507 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Preuve Algebrique Du Critere De Planarite De Wu-Liu / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Toward a theory of crossing numbers / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Embedding Graphs in the Plane—Algorithmic Aspects / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/bf02579375 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1989666671 / rank | |||
Normal rank |
Latest revision as of 11:00, 30 July 2024
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