# Practical importance of interval / circular-arc graphs in resource allocation

A graph is called a circular-arc graph if each of its vertices can be assigned to a circular arc such that two vertices are adjacent iff their respective arcs have a non-empty intersection. Analogously, a graph is an interval graph if we can assign each of its vertices to intervals on a line in the above fashion. Note that interval graphs are a subclass of circular-arc graphs.

Wikipedia states that interval/circular-arc graphs are important in the modeling of (periodic) resource allocations problems in operations research. Can you provide a concrete example of such a problem and how it is modeled to CA/interval graphs? The problem should conceivably occur in practice.

• If you think about the intervals as times when certain jobs need to be done, then the graph with an edge between two jobs that have overlap in their active times are interval graphs or circular arc graphs. – Louis May 11 '14 at 19:06
• I don't have a concrete application, or I'd make an answer, but I assume that this is the idea. – Louis May 11 '14 at 19:31

Given a set of intervals (interval system) $\mathcal{I} = \{ [x_1, x_2] ,\dots, [x_{2n-1}, x_{2n}] \}$. Each of the $n$ intervals corresponds to the time period a certain job is being worked on. Now, we want to find all time periods in which the number of concurrently active jobs is maximal. These time periods happen to correspond to the maxcliques of maximal size of the intersection graph $G(\mathcal{I}) = (\mathcal{I} , E)$ with $E$ being defined as $$([a,b] , [c,d]) \in E \iff [a,b] \cap [c,d] \neq \emptyset$$ The closed neighborhood of a vertice $v$ in a graph $G$ is defined as $$N[v] := \{ u \in V(G) : \{v,u\} \in E \} \cup \{v\}$$ It is known that for any interval graph every maxclique can be characterized as the intersection of two neighborhoods, i.e. for each maxclique $C$ of $G$ there exist some $u,v \in V(G)$ s.t. $C = N[u] \cap N[v]$.