Algorithms and outerplanar conditions for \(A\)-trails in plane Eulerian graphs (Q1392551)

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.