Algorithms and outerplanar conditions for \(A\)-trails in plane Eulerian graphs (Q1392551): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 16:57, 31 January 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