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 R$

be a set of intervals. Then the corresponding interval 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 \emptyset .$