Circular-arc graph

demonstrated the first polynomial recognition algorithm for circular-arc graphs, which runs in {\mathcal O}(n^3) time. gave the first linear ({\mathcal O}(n+m)) time recognition algorithm, where m 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 always perfect, as the odd chordless cycles C5, C7, etc., are circular-arc graphs. == Some subclasses ==

In the following, let G = (V,E) be an arbitrary graph. Unit circular-arc graphs G 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 (n+2)\binom{2n-1}{n-1}-2^{2n-1}. Proper circular-arc graphs G is a proper circular-arc graph (also known as a circular interval graph) 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 ({\mathcal O}(n + m)) time. They form one of the fundamental subclasses of the claw-free graphs. Helly circular-arc graphs G 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 {\mathcal O(n^3)} 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==