Unit Circular-Arc Graph Representations and Feasible Circulations
Min Chih Lin, Jayme Luiz SZWARCFITER · SIAM Journal on Discrete Mathematics · 2008
In a recent paper, Durán et al. [J. Algorithms, 58 (2006), pp. 67–78] 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 Deng, Hell, and Huang [SIAM J. Comput., 25 (1996), pp. 390–403]. 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.