Reference for mixed graph acyclicity testing algorithm?
Finding mixed cycles in a mixed graph is equivalent to finding elementary directed cycles (of length >=3) in the corresponding directed graph. The corresponding directed graph is obtained from the mixed graph by replacing each undirected edge by two directed edges pointing in opposite directions. Proof: (1) Each elementary directed cycle (of length >=3) in the digraph corresponds directly to a mixed cycle in the mixed graph. (2) Each mixed cycle in the mixed graph contains an elementary mixed cycle of length >=3, and each such cycle corresponds directly an elementary directed cycle (of length >=3) in the directed graph. (1) and (2) together prove both directions of the statement, qed. So we are looking for references how to compute (all?) elementary cycles (of length >=3) in a directed graph.

The comments indicate that cs.stackexchange contains some answers to this question, but it is unclear how to organize the results into a concise answer. This blog post seems to nicely summarize the (most?) important references:


  Algorithm by R. Tarjan
  
  The earliest algorithm that I included was published by R. Tarjan in 1973.

Enumeration of the elementary circuits of a directed graph
R. Tarjan, SIAM Journal on Computing, 2 (1973), pp. 211-216
http://dx.doi.org/10.1137/0202017

  
  Algorithm by D. B. Johnson
  
  The algorithm by D. B. Johnson from 1975 improves on Tarjan's algorithm by its complexity.

Finding all the elementary circuits of a directed graph.
D. B. Johnson, SIAM Journal on Computing 4, no. 1, 77-84, 1975.
http://dx.doi.org/10.1137/0204007

  
  In the worst case, Tarjan's algorithm has a time complexity of O(n⋅e(c+1)) whereas Johnson's algorithm supposedly manages to stay in O((n+e)(c+1)) where n is the number of vertices, e is the number of edges and c is the number of cycles in the graph.
  
  Algorithm by K. A. Hawick and H. A. James
  
  The algorithm by K. A. Hawick and H. A. James from 2008 improves further on Johnson's algorithm and does away with its limitations.

Enumerating Circuits and Loops in Graphs with Self-Arcs and Multiple-Arcs.
Hawick and H.A. James, In Proceedings of FCS. 2008, 14-20
www.massey.ac.nz/~kahawick/cstn/013/cstn-013.pdf
http://complexity.massey.ac.nz/cstn/013/cstn-013.pdf

  
  In contrast to Johnson's algorithm, the algorithm by K. A. Hawick and H. A. James is able to handle graphs containing edges that start and end at the same vertex as well as multiple edges connecting the same two vertices.


The acyclicity testing itself seems to be easy: Compute the strongly connected components of the graph. Any (elementary) cycle is completely contained in a strongly connected component. A strongly connected component contains an elementary cycle iff it is not an undirected tree.

David Eppstein's proposed algorithm additionally computes one elementary cycle as evidence, and the above algorithms enumerate all elementary cycles. Any vertex or edge not contained in an elementary cycle could be deleted as a preprocessing step to improve the speed of the above algorithms. David Eppstein's algorithm could be used for that purpose, but even if only used on the strongly connected components, it won't delete every possible vertex or edge that can be deleted. But even if it could be extended to do so (computing the block-cut tree at least allows to delete every possible vertex that can be deleted), it is unclear whether this would really improve the speed of the above algorithms.