Summary: G. Durán et al. [J. Algorithms 58, No. 1, 67–78 (2006; Zbl 1093.68071)] described an algorithm of complexity \(O(n^2)\) for recognizing whether a graph \(G\) with \(n\) vertices and \(m\) edges is a unit circular-arc (UCA) graph. Furthermore, the following open questions were posed in the above paper:

(i)

Is it possible to construct a UCA model for \(G\) in polynomial time?

(ii)

Is it possible to construct a UCA model, whose extremes of the arcs correspond to integers of polynomial size?

(iii)

If (ii) is true, could such a model be constructed in polynomial time?

In the present paper, we describe a characterization of UCA graphs, based on network circulations. The characterization leads to a different recognition algorithm and to answering these questions in the affirmative. We construct a UCA model whose extremes of the arcs correspond to integers of size \(O(n)\). The proposed algorithms, for recognizing UCA graphs and constructing UCA models, have complexities \(O(n+m)\). Furthermore, the complexities reduce to \(O(n)\), if a proper circular-arc (PCA) model of \(G\) is already given as the input, provided the extremes of the arcs are ordered. We remark that a PCA model of \(G\) can be constructed in \(O(n+m)\) time, using the algorithm by X. Deng, P. Hell and J. Huang [SIAM J. Comput. 25, 390–403 (1996; Zbl 0858.05094)].
Finally, we also describe a linear time algorithm for finding feasible circulations in networks with nonnegative lower capacities and unbounded upper capacities. Such an algorithm is employed in the model construction for UCA graphs.