Reconnaissance des graphes de cordes
type: Item
instance of: scholarly article
title: Reconnaissance des graphes de cordes
zbMATH Open document ID: 0567.05033
DOI: 10.1016/0012-365X(85)90117-7
author: Walid Naji
published in: Discrete Mathematics
publication date: 1985-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 3904621
zbMATH Keywords: circle graph
zbMATH Keywords: chords
zbMATH Keywords: orientation
zbMATH Keywords: double labelling
reviewed by: Philippe Vincke
MaRDI profile type: Publication
cites work: Q5422499
cites work: Q4156464
cites work: A characterization of circle graphs
cites work: Q3328583
description: scientific article; zbMATH DE number 3904621