The NP-completeness of finding A-trails in Eulerian graphs and of finding spanning trees in hypergraphs (Q1893154)

This paper proves that it is NP-complete to decide whether a simple, 3- connected, plane Eulerian graph for which all face boundaries are 3- cycles or 4-cycles as an A-trail, that is, an Eulerian trail in which successive edges are always neighbours in the cyclic, clockwise ordering defined at each vertex of the graph by the given plane representation and a linear hypergraph which is regular of degree 3 has a spanning tree.