Recognition
demonstrated the first polynomial recognition algorithm for circular-arc graphs, which runs in time. gave the first linear time recognition algorithm, where is the number of edges. More recently, Kaplan and Nussbaum developed a simpler linear time recognition algorithm.Relation to other graph classes
Circular-arc graphs are a natural generalization of interval graphs. If a circular-arc graph ''G'' has an arc model that leaves some point of the circle uncovered, the circle can be cut at that point and stretched to a line, which results in an interval representation. Unlike interval graphs, however, circular-arc graphs are not alwaysSome subclasses
In the following, let be an arbitrary graph.Unit circular-arc graphs
is a unit circular-arc graph if there exists a corresponding arc model such that each arc is of equal length. The number of labelled unit circular-arc graphs on ''n'' vertices is given by .Proper circular-arc graphs
is a proper circular-arc graph (also known as a circular interval graph)Described with a different but equivalent definition by . if there exists a corresponding arc model such that no arc properly contains another. Recognizing these graphs and constructing a proper arc model can both be performed in linear time. pg. ? They form one of the fundamental subclasses of the claw-free graphs.Helly circular-arc graphs
is a Helly circular-arc graph if there exists a corresponding arc model such that the arcs constitute a Helly family. gives a characterization of this class that implies an recognition algorithm. give other characterizations of this class, which imply a recognition algorithm that runs in ''O(n+m)'' time when the input is a graph. If the input graph is not a Helly circular-arc graph, then the algorithm returns a certificate of this fact in the form of a forbidden induced subgraph. They also gave an ''O(n)'' time algorithm for determining whether a given circular-arc model has the Helly property.Applications
Circular-arc graphs are useful in modeling periodic resource allocation problems in operations research. Each interval represents a request for a resource for a specific period repeated in time.Notes
References
*. *. * . * . Second edition, ''Annals of Discrete Mathematics'' 57, Elsevier, 2004. *. * . * {{citation , last = Tucker , first = Alan , authorlink=Alan Tucker , title = An efficient test for circular-arc graphs , journal = SIAM Journal on Computing , volume = 9 , year = 1980 , issue = 1 , pages = 1–24 , doi = 10.1137/0209001.External links