Circular-arc graph

A circular-arc graph (left) and a set of circular arcs representing it (right).

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

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

be a set of arcs. 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.

External links

• "circular arc graph". Information System on Graph Class Inclusions. {{cite web}}: External link in |work= (help)