Reconnaissance des graphes de cordes (Q1059643)

A simple graph \(G=(V,E)\) is a circle graph if one can associate to G a diagram C(V), consisting of a circle C together with a set V of chords of C, in such a way that adjacency of vertices corresponds to crossing of corresponding chords. An orientation of a chord x of C(V) allows us to define the left side and the right side of x. The relation: ''The initial end of the chord x is on the left side of the chord y'' associated to an arbitrary orientation of the chords of C(V) gives an orientation of the edges of G and a double labelling of the edges of the complementary graph \(\bar G.\) The author studies the combinatorial relationships between such an orientation and such a double labelling. A characterization of circle graphs which yields a polynomial time recognition algorithm is also obtained.