Partial Characterizations of Circle Graphs

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

Cartagena de Indias, Colombia

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

ALIO (Asiciación Latino-Ibero Americana de Investigación de Operaciones)

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.