zbMATH — the first resource for mathematics

Reconnaissance des graphes de cordes. (French) Zbl 0567.05033
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.
Reviewer: Ph.Vincke

05C38 Paths and cycles
05C20 Directed graphs (digraphs), tournaments
Full Text: DOI
[1] Bondy, J.A; Murty, U.S.R, Graph theory with applications, (1976), MacMillan London · Zbl 1134.05001
[2] Fournier, J.C, Une caractérisation des graphes de cordes, C.R. acad. sci. Paris, 811-813, (1978) · Zbl 0378.05045
[3] H. De Fraysseix, A characterization of circle-graphs, a paraître. · Zbl 0551.05056
[4] Golumbic, M.C, Algorithmic graph theory and perfect graphs, (1980), Academic Press New York, Ch. 11 · Zbl 0541.05054
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.