Circular-arc graph

${\displaystyle 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 ${\displaystyle (n+2){\binom {2n-1}{n-1}}-2^{2n-1}}$. [2]

${\displaystyle G}$ 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 ${\displaystyle ({\mathcal {O}}(n+m))}$ time.[4] They form one of the fundamental subclasses of the claw-free graphs.[3]

${\displaystyle G}$ is a Helly circular-arc graph if there exists a corresponding arc model such that the arcs constitute a Helly family. Gavril (1974) gives a characterization of this class that implies an ${\displaystyle {{\mathcal {O}}(n^{3})}}$ recognition algorithm.

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.