Artículo

Structural results on circular-arc graphs and circle graphs: a survey and the main open problems

Duran, Guillermo AlfredoIcon ; Grippo, Luciano NorbertoIcon ; Safe, Martin DarioIcon
Fecha de publicación: 02/2014
Editorial: Elsevier Science
Revista: Discrete Applied Mathematics
ISSN: 0166-218X
Idioma: Inglés
Tipo de recurso: Artículo publicado
Clasificación temática:

Resumen

Circular-arc graphs are the intersection graphs of open arcs on a circle. Circle graphs are the intersection graphs of chords on a circle. These graph classes have been the subject of much study for many years and numerous interesting results have been reported. Many subclasses of both circular-arc graphs and circle graphs have been defined and different characterizations formulated. In this survey, we summarize the most important structural results related to circular-arc graphs and circle graphs and present the main open problems.
Palabras clave: Circle Graphs , Circular-Arc Graphs , Forbidden Subgraph Characterizations , Interval Graphs , Matrix Characterizations , Permutation Graphs
 
Archivos asociados
Thumbnail
 
Tamaño: 614.6Kb
Formato: PDF
.
Licencia
info:eu-repo/semantics/openAccess Excepto donde se diga explícitamente, este item se publica bajo la siguiente descripción: Atribución-NoComercial-SinDerivadas 2.5 Argentina (CC BY-NC-ND 2.5 AR)
Identificadores
URI: http://hdl.handle.net/11336/30477
DOI: http://dx.doi.org/10.1016/j.dam.2012.12.021
URL: http://www.sciencedirect.com/science/article/pii/S0166218X13000103
Colecciones
Articulos(OCA CIUDAD UNIVERSITARIA)
Articulos de OFICINA DE COORDINACION ADMINISTRATIVA CIUDAD UNIVERSITARIA
Citación
Duran, Guillermo Alfredo; Grippo, Luciano Norberto; Safe, Martin Dario; Structural results on circular-arc graphs and circle graphs: a survey and the main open problems; Elsevier Science; Discrete Applied Mathematics; 164; Part 2; 2-2014; 427-444
Compartir
Altmétricas