Algorithms and outerplanar conditions for \(A\)-trails in plane Eulerian graphs (Q1392551): Difference between revisions
From MaRDI portal
Created a new Item |
Set OpenAlex properties. |
||
(5 intermediate revisions by 4 users not shown) | |||
Property / reviewed by | |||
Property / reviewed by: Gregory Gutin / rank | |||
Property / reviewed by | |||
Property / reviewed by: Gregory Gutin / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The NP-completeness of finding A-trails in Eulerian graphs and of finding spanning trees in hypergraphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5545841 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The importance of being Euler / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Eulerian graphs and related topics. Part 1, Volume 1 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4121921 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Theorem on Planar Graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3785974 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2049344114 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 11:35, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Algorithms and outerplanar conditions for \(A\)-trails in plane Eulerian graphs |
scientific article |
Statements
Algorithms and outerplanar conditions for \(A\)-trails in plane Eulerian graphs (English)
0 references
28 July 1998
0 references
An \(A\)-trail in a plane Eulerian multigraph is an Eulerian trail with the property that consecutive edges of the trail, say \((v_{i-1}, v_i)\) and \((v_i, v_{i+1})\), are always neighbours in the cyclic ordering of the edges incident with \(v_i\) defined by the clockwise order in the plane representation. The problem of finding \(A\)-trails in plane Eulerian graphs is NP-complete even for 3-connected graphs. Some sufficient conditions for the existence of \(A\)-trails are proved. Algorithmic aspects are discussed.
0 references
plane graphs
0 references
outerplanar graphs
0 references
\(A\)-trail
0 references
Eulerian trail
0 references
plane Eulerian graphs
0 references
0 references