On Intersection Graphs of Arcs and Chords in a Circle

Abstract

Circular-arc graphs are the intersection graphs of arcs on a circle. We review in this thesis the main results known about this class and we analize some subclasses of it. We show new characterizations for proper circular-arc graphs derived from a characterization formulated by Tucker, and we deduce minimal forbidden structures for circular arc-graphs.All possible intersections of the defined subclasses are studied, showing a minimal example in each one of the generated regions, except one of them that we prove it is empty. From here, we conclude that a clique-Helly and proper no unit circular-arc graph must be Hellycircular-arc graph.Circle graphs are the intersection graphs of chords in a circle. We present also a review of the main results in this class and define the most important subclasses, proving some relations of inclusions between them.We prove a neccesary condition so that a graph is a Helly circle graph and conjecture thatthis condition is sufficient too. If this conjecture becomes true, we would have acharacterization and a polynomial recognition for this subclass.Minimal forbidden structures for circle graphs are shown, using the chacterization of propercircular-arc graphs by Tucker and a characterization theorem for circle graphs by Bouchet.We also analize all the possible intersections between the defined subclasses of circlegraphs, showing a minimal example in each generated region.A superclass of circle graphs is studied: overlap graphs of circular-arc graphs. We show new properties on this class, analizing its relation with circle and circular-arc graphs. A necessary condition for a graph being an overlap graph of circular-arc graphs is shown. We prove that the problem of finding a minimum clique partition for the class of graphs which does not contain either odd holes, or a 3-fan, or a 4-wheel as induced subgraphs, can be solved in polynomial time. We use in the proof results of polyhedral theory for integer linear programming. We extend this result for minimum clique covering by vertices. These results are applied for Helly circle graphs without odd holes. We also show that the problem of minimum clique covering by vertices can be solved in polynomial time for Helly circular-arc graphs. Finally, we present some interesting problems which remain open.