Proper Helly circular-arc graphs

A circular-arc model M = (C, A) is a circle C together with a collection A of arcs of C. If no arc is contained in any other then M is a proper circular-arc model, if every arc has the same length then M is a unit circular-arc model and if A satisfies the Helly Property then M is a Helly circular-ar...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Lin, Min Chih, Soulignac, Francisco Juan
Publicado:	2007
Materias:	Algorithms Forbidden subgraphs Helly circular-arc graphs Proper circular-arc graphs Unit circular-arc graphs Linear programming Mathematical models Graph theory
Acceso en línea:	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v4769LNCS_n_p248_Lin http://hdl.handle.net/20.500.12110/paper_03029743_v4769LNCS_n_p248_Lin
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	paper:paper_03029743_v4769LNCS_n_p248_Lin
record_format	dspace
spelling	paper:paper_03029743_v4769LNCS_n_p248_Lin2023-06-08T15:28:26Z Proper Helly circular-arc graphs Lin, Min Chih Soulignac, Francisco Juan Algorithms Forbidden subgraphs Helly circular-arc graphs Proper circular-arc graphs Unit circular-arc graphs Algorithms Linear programming Mathematical models Forbidden subgraphs Helly circular-arc graphs Proper circular-arc graphs Unit circular-arc graphs Graph theory A circular-arc model M = (C, A) is a circle C together with a collection A of arcs of C. If no arc is contained in any other then M is a proper circular-arc model, if every arc has the same length then M is a unit circular-arc model and if A satisfies the Helly Property then M is a Helly circular-arc model. A (proper) (unit) (Helly) circular-arc graph is the intersection graph of the arcs of a (proper) (Helly) circular-arc model. Circular-arc graphs and their subclasses have been the object of a great deal of attention in the literature. Linear time recognition algorithms have been described both for the general class and for some of its subclasses. In this article we study the circular-arc graphs which admit a model which is simultaneously proper and Helly. We describe characterizations for this class, including one by forbidden induced subgraphs. These characterizations lead to linear time certifying algorithms for recognizing such graphs. Furthermore, we extend the results to graphs which admit a model which is simultaneously unit and Helly, also leading to characterizations and a linear time certifying algorithm. © Springer-Verlag Berlin Heidelberg 2007. Fil:Lin, M.C. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Soulignac, F.J. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2007 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v4769LNCS_n_p248_Lin http://hdl.handle.net/20.500.12110/paper_03029743_v4769LNCS_n_p248_Lin
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-134
collection	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic	Algorithms Forbidden subgraphs Helly circular-arc graphs Proper circular-arc graphs Unit circular-arc graphs Algorithms Linear programming Mathematical models Forbidden subgraphs Helly circular-arc graphs Proper circular-arc graphs Unit circular-arc graphs Graph theory
spellingShingle	Algorithms Forbidden subgraphs Helly circular-arc graphs Proper circular-arc graphs Unit circular-arc graphs Algorithms Linear programming Mathematical models Forbidden subgraphs Helly circular-arc graphs Proper circular-arc graphs Unit circular-arc graphs Graph theory Lin, Min Chih Soulignac, Francisco Juan Proper Helly circular-arc graphs
topic_facet	Algorithms Forbidden subgraphs Helly circular-arc graphs Proper circular-arc graphs Unit circular-arc graphs Algorithms Linear programming Mathematical models Forbidden subgraphs Helly circular-arc graphs Proper circular-arc graphs Unit circular-arc graphs Graph theory
description	A circular-arc model M = (C, A) is a circle C together with a collection A of arcs of C. If no arc is contained in any other then M is a proper circular-arc model, if every arc has the same length then M is a unit circular-arc model and if A satisfies the Helly Property then M is a Helly circular-arc model. A (proper) (unit) (Helly) circular-arc graph is the intersection graph of the arcs of a (proper) (Helly) circular-arc model. Circular-arc graphs and their subclasses have been the object of a great deal of attention in the literature. Linear time recognition algorithms have been described both for the general class and for some of its subclasses. In this article we study the circular-arc graphs which admit a model which is simultaneously proper and Helly. We describe characterizations for this class, including one by forbidden induced subgraphs. These characterizations lead to linear time certifying algorithms for recognizing such graphs. Furthermore, we extend the results to graphs which admit a model which is simultaneously unit and Helly, also leading to characterizations and a linear time certifying algorithm. © Springer-Verlag Berlin Heidelberg 2007.
author	Lin, Min Chih Soulignac, Francisco Juan
author_facet	Lin, Min Chih Soulignac, Francisco Juan
author_sort	Lin, Min Chih
title	Proper Helly circular-arc graphs
title_short	Proper Helly circular-arc graphs
title_full	Proper Helly circular-arc graphs
title_fullStr	Proper Helly circular-arc graphs
title_full_unstemmed	Proper Helly circular-arc graphs
title_sort	proper helly circular-arc graphs
publishDate	2007
url	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v4769LNCS_n_p248_Lin http://hdl.handle.net/20.500.12110/paper_03029743_v4769LNCS_n_p248_Lin
work_keys_str_mv	AT linminchih properhellycirculararcgraphs AT soulignacfranciscojuan properhellycirculararcgraphs
_version_	1768542219411652608

Proper Helly circular-arc graphs

Ejemplares similares