Normal Helly circular-arc graphs and its subclasses
A Helly circular-arc model M=(C,A) is a circle C together with a Helly family A of arcs of C. If no arc is contained in any other, then M is a proper Helly circular-arc model, if every arc has the same length, then M is a unit Helly circular-arc model, and if there are no two arcs covering the circl...
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | JOUR |
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_0166218X_v161_n7-8_p1037_Lin |
| Aporte de: |
| id |
todo:paper_0166218X_v161_n7-8_p1037_Lin |
|---|---|
| record_format |
dspace |
| spelling |
todo:paper_0166218X_v161_n7-8_p1037_Lin2023-10-03T15:03:41Z Normal Helly circular-arc graphs and its subclasses Lin, M.C. Soulignac, F.J. Szwarcfiter, J.L. Helly circular-arc graphs Normal circular-arc graphs Proper circular-arc graphs Unit circular-arc graphs Circular-arc graph Forbidden induced subgraphs If there are Intersection graph Interval graph Natural generalization Proper circular-arc graphs Unit circular-arc graphs Algorithms Characterization Graph theory Graphic methods A Helly circular-arc model M=(C,A) is a circle C together with a Helly family A of arcs of C. If no arc is contained in any other, then M is a proper Helly circular-arc model, if every arc has the same length, then M is a unit Helly circular-arc model, and if there are no two arcs covering the circle, then M is a normal Helly circular-arc model. A Helly (resp. proper Helly, unit Helly, normal Helly) circular-arc graph is the intersection graph of the arcs of a Helly (resp. proper Helly, unit Helly, normal Helly) circular-arc model. In this article we study these subclasses of Helly circular-arc graphs. We show natural generalizations of several properties of (proper) interval graphs that hold for some of these Helly circular-arc subclasses. Next, we describe characterizations for the subclasses of Helly circular-arc graphs, including forbidden induced subgraphs characterizations. These characterizations lead to efficient algorithms for recognizing graphs within these classes. Finally, we show how these classes of graphs relate with straight and round digraphs. © 2012 Elsevier B.V. All rights reserved. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_0166218X_v161_n7-8_p1037_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 |
Helly circular-arc graphs Normal circular-arc graphs Proper circular-arc graphs Unit circular-arc graphs Circular-arc graph Forbidden induced subgraphs If there are Intersection graph Interval graph Natural generalization Proper circular-arc graphs Unit circular-arc graphs Algorithms Characterization Graph theory Graphic methods |
| spellingShingle |
Helly circular-arc graphs Normal circular-arc graphs Proper circular-arc graphs Unit circular-arc graphs Circular-arc graph Forbidden induced subgraphs If there are Intersection graph Interval graph Natural generalization Proper circular-arc graphs Unit circular-arc graphs Algorithms Characterization Graph theory Graphic methods Lin, M.C. Soulignac, F.J. Szwarcfiter, J.L. Normal Helly circular-arc graphs and its subclasses |
| topic_facet |
Helly circular-arc graphs Normal circular-arc graphs Proper circular-arc graphs Unit circular-arc graphs Circular-arc graph Forbidden induced subgraphs If there are Intersection graph Interval graph Natural generalization Proper circular-arc graphs Unit circular-arc graphs Algorithms Characterization Graph theory Graphic methods |
| description |
A Helly circular-arc model M=(C,A) is a circle C together with a Helly family A of arcs of C. If no arc is contained in any other, then M is a proper Helly circular-arc model, if every arc has the same length, then M is a unit Helly circular-arc model, and if there are no two arcs covering the circle, then M is a normal Helly circular-arc model. A Helly (resp. proper Helly, unit Helly, normal Helly) circular-arc graph is the intersection graph of the arcs of a Helly (resp. proper Helly, unit Helly, normal Helly) circular-arc model. In this article we study these subclasses of Helly circular-arc graphs. We show natural generalizations of several properties of (proper) interval graphs that hold for some of these Helly circular-arc subclasses. Next, we describe characterizations for the subclasses of Helly circular-arc graphs, including forbidden induced subgraphs characterizations. These characterizations lead to efficient algorithms for recognizing graphs within these classes. Finally, we show how these classes of graphs relate with straight and round digraphs. © 2012 Elsevier B.V. All rights reserved. |
| format |
JOUR |
| author |
Lin, M.C. Soulignac, F.J. Szwarcfiter, J.L. |
| author_facet |
Lin, M.C. Soulignac, F.J. Szwarcfiter, J.L. |
| author_sort |
Lin, M.C. |
| title |
Normal Helly circular-arc graphs and its subclasses |
| title_short |
Normal Helly circular-arc graphs and its subclasses |
| title_full |
Normal Helly circular-arc graphs and its subclasses |
| title_fullStr |
Normal Helly circular-arc graphs and its subclasses |
| title_full_unstemmed |
Normal Helly circular-arc graphs and its subclasses |
| title_sort |
normal helly circular-arc graphs and its subclasses |
| url |
http://hdl.handle.net/20.500.12110/paper_0166218X_v161_n7-8_p1037_Lin |
| work_keys_str_mv |
AT linmc normalhellycirculararcgraphsanditssubclasses AT soulignacfj normalhellycirculararcgraphsanditssubclasses AT szwarcfiterjl normalhellycirculararcgraphsanditssubclasses |
| _version_ |
1807319787616862208 |