Circular-arc graph
In graph theory, a circular-arc graph is the intersection graph of a set of arcs on the circle. It has one vertex for each arc in the set, and an edge between every pair of vertices corresponding to arcs that intersect. Formally, let be a set of arcs. Then the corresponding circular-arc graph is "G" = ("V", "E") where and A family of arcs that corresponds to G is called an "arc model". Recognition. demonstrated the first polynomial recognition algorithm for circular-arc graphs, which runs in formula_4 time. gave the first linear formula_5 time  recognition algorithm, where formula_6 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 "C", "C", etc., are circular-arc graphs. Some subclasses. In the  following, let formula_7 be an arbitrary graph. Unit circular-arc graphs. formula_8 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 formula_9. Proper circular-arc graphs. formula_8 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 formula_11 time. They form one  of the fundamental subclasses of the claw-free graphs. Helly circular-arc graphs. formula_8 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 formula_13 recognition algorithm. 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.