Circular-arc graph

Tucker (1980) demonstrated the first polynomial recognition algorithm for circular-arc graphs, which runs in

More recently, Kaplan and Nussbaum[1] developed a simpler linear time recognition algorithm.

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.

The number of labelled unit circular-arc graphs on n vertices is given by

is a proper circular-arc graph (also known as a circular interval graph)[3] 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

[4] They form one of the fundamental subclasses of the claw-free graphs.

Gavril (1974) gives a characterization of this class that implies an

Joeris et al. (2009) 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.

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.