On Intersection Graphs of Arcs and Chords in a Circle

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...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Durán, Guillermo A.
Formato: Articulo Contribucion a revista
Lenguaje:Inglés
Publicado: 2000
Materias:
Ciencias Informáticas
circular-arc graphs
subclasses
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/135471
https://publicaciones.sadio.org.ar/index.php/EJS/article/view/128
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-135471
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Inglés
topic Ciencias Informáticas
circular-arc graphs
subclasses
spellingShingle Ciencias Informáticas
circular-arc graphs
subclasses
Durán, Guillermo A.
On Intersection Graphs of Arcs and Chords in a Circle
topic_facet Ciencias Informáticas
circular-arc graphs
subclasses
description 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.
format Articulo
Contribucion a revista
author Durán, Guillermo A.
author_facet Durán, Guillermo A.
author_sort Durán, Guillermo A.
title On Intersection Graphs of Arcs and Chords in a Circle
title_short On Intersection Graphs of Arcs and Chords in a Circle
title_full On Intersection Graphs of Arcs and Chords in a Circle
title_fullStr On Intersection Graphs of Arcs and Chords in a Circle
title_full_unstemmed On Intersection Graphs of Arcs and Chords in a Circle
title_sort on intersection graphs of arcs and chords in a circle
publishDate 2000
url http://sedici.unlp.edu.ar/handle/10915/135471
https://publicaciones.sadio.org.ar/index.php/EJS/article/view/128
work_keys_str_mv AT duranguillermoa onintersectiongraphsofarcsandchordsinacircle
bdutipo_str Repositorios
_version_ 1764820455396474881

Ejemplares similares