On non-intersecting Eulerian circuits
The following question arises in flame-cutting and similar applications. ''Given a graph drawn in the plane, is there an Eulerian circuit in which successive edges always belong to a common face?'' We prove that this question and related ones are NP-complete.
scientific article; zbMATH DE number 4006297