Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419021 | Discrete Applied Mathematics | 2014 | 17 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Guillermo Durán, Luciano N. Grippo, Martín D. Safe,