Circular-arc graph

In graph theory, a circular-arc graph is the intersection graph of a set of intervals on the circle. It has one vertex for each interval in the set, and an edge between every pair of vertices corresponding to intervals that intersect.

Formally, let

$I_{1},I_{2},\ldots ,I_{n}\subset C_{1}$

be a set of intervals. Then the corresponding circular arc graph is G = (V, E) where

$V=\{I_{1},I_{2},\ldots ,I_{n}\}$

and

$\{I_{\alpha },I_{\beta }\}\in E\iff I_{\alpha }\cap I_{\beta }\neq \varnothing .$

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.