A double occurrence word is a circular string of length $2n$ over an alphabet of size $n$ with each letter occurring exactly twice, for example:
ABACCDBD
Given a double occurrence word, we can form a graph with vertex set the alphabet, and where two vertices $u$, $v$ are adjacent if the symbols occur interleaved in the double occurrence word, i.e., $uvuv$ rather than $uuvv$.
For the example double occurrence word above, we have
ABA...B.
and so A is adjacent to B, but
A.ACC...
and so A is not adjacent to C.
Graphs arising from double-occurrence words are called circle graphs.
(This terminology arises from imagining the string laid out around a circle, with $n$ chords, each joining the two occurrences of a symbol. Then two chords cross if and only if the two corresponding symbols interleave. So a circle graph is just the intersection graph of chords of a fixed circle.)
There are a number of articles, most of which are longish, giving polynomial-time recognition algorithms for circle graphs—in other words, the input is a graph (just as a list of edges or adjacency matrix) and the output is either "No this is not a circle graph" or a double occurrence word verifying that it is a circle graph.
Question: Is there a publicly accessible implementation of one of these algorithms anywhere?
Edit Here is an accessible reference, which will refer to previous work, by Spinrad and by Gabor, Supowit and Hsu (the latter two may not be accessible without appropriate subscriptions).
Gioan, Paul, Tedder, Corneil — https://arxiv.org/abs/1104.3284
