# Two-chordless cycle extraction from a failed comparability graph recognition

I have implemented a comparability graph recognition algorithm from M.C. Golumbic's "Algorithmic graph theory and perfect graphs" book. It is hinted in Fekete, Schepers, and van der Veen's "Exact Algorithm for Higher-Dimensional Orthogonal Packing" paper that the algorithm can be modified such that given the negative recognition result you can obtain a two-chordless cycle. But it is not explained how it is done and my knowledge on graph theory isn't anything special.

My current intuition is that if the recognition algorithm fails at level $k$ then a cycle must have been created where a transitive orientation is not possible. And this would mean the set of edges at the point of failure at level $k$ would induce a subgraph that contains the cycle I'm looking for, and then I just need to prune away the edges that have no involvment with the cycle created.

My questions: Is my intuition correct and if not, what does Fekete, Schepers, and van der Veen's "simple to modify" hint mean?

I'm doing this for efficiency, I want to obtain two results with one algorithmic search.

import networkx as nx

def comparability(G):
classification = dict()
k = 0
def explore(i, j):
# k and classification from outer function
classtest = lambda e: e in classification and abs(classification[e]) != k
if m not in adjacent_J or classtest((j, m)):
if (i, m) not in classification:
classification[(i, m)] = k
classification[(m, i)] = -k
if not explore(i, m):
return False
elif (i, m) in classification and classification[(i, m)] == -k:
return False
if m not in adjacent_I or classtest((i, m)):
if (m, j) not in classification:
classification[(m, j)] = k
classification[(j, m)] = -k
if not explore(m, j):
return False
elif (m, j) in classification and classification[(m, j)] == -k:
return False
return True
for i, j in G.edges():
if (i, j) not in classification:
k += 1
classification[(i, j)] = k
classification[(j, i)] = -k
if not explore(i, j):
return False, classification
return True, classification

G = nx.Graph()