Algorithms and outerplanar conditions for \(A\)-trails in plane Eulerian graphs (Q1392551): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
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 |
Revision as of 13:28, 28 May 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