# Are there classes where all Eulerian orientations can be listed in polynomial time?

Is there is a subclass of regular graphs (say 4-regular graphs) for which there is a polynomial time algorithm to list all Eulerian orienations?

An Eulerian orientaiton of an (undirected simple) graph $$G$$ is an orientation of $$G$$ such that every vertex has in-degree equal to out-degree. Obviously, a graph must be an even regular graph to admit an Eulerian orientation. Also, one can find an Eulerian orientation of an even regular graph by taking a directed Euler tour and orienting the edges in the direction of the tour.

The problem of counting Eulerian orientations of a 4-regular graph is studied in graph polynomials context [equivalent to evaluating the Tutte polynomial at the point (0, -2)], flow theory (equivalent to counting the number of maximum flows around a network) and in statistical physics (ice-type models). The counting problem is hard (#P-complete), but there are efficent approximation algorithms.

Naturally, listing all Euler orienations is hard. I have a problem which could be solved if we have the list of all Eulerian orienations (there is a one-one map from a set of objects I study to the set of Eulerian orienations of a fixed graph $$G$$). If it matters, we know that (i) $$G$$ can be decomposed into cycles of length divisible by three and (ii) $$G$$ is (diamond,$$K_4$$)-free.

I wonder whether there is a subclass of regular graphs in which the listing problem is polynomial time solvable. I would expect this class to be small (but it should be non-trivial to be of interest).

Is there a paper that deal with listing Eulerian orientaitons?

Thank you.