Partial characterizations of circle graphs

BONOMO, FLAVIA; DURÁN, GUILLERMO; GRIPPO, LUCIANO NORBERTO; SAFE, MARTÍN DARÍO

Cartagena de Indias

Congreso; XIV Latin-Iberian American Congress of Operations Research (CLAIO); 2008

A graph is a circle graph if it is the intersection graph of a family of chords on a circle. We give a forbidden induced subgraph characterization of circle graphs restricted to graphs that belong to one of the following graph classes: linear domino, {chair,triangle}-free, P_4-sparse and tree-cographs. A graph is Helly circle if it has a circle model whose chords satisfy the Helly property. Wecharacterize Helly circle graphs by the existence of real solutions of a system of polynomial equations and inequalities. Finally, we characterize unit Helly circle which are those having a circle model whose chords have the same length and satisfy the Helly property.