Linear-time representation algorithms for proper circular-arc graphs and proper interval graphs

Our main result is a linear-time (that is, time O(m + n)) algorithm to recognize and represent proper circular-are graphs. The best previous algorithm, due to A. Tucker, has time complexity O(n(2)). We take advantage of the fact that (among connected graphs) proper circular-arc graphs are precisely the graphs orientable as local tournaments, and we use a new characterization of local tournaments. The algorithm depends on repeated representation of portions of the input graph as proper interval graphs. Thus we also find it useful to give a new linear-time algorithm to represent proper interval graphs. This latter algorithm also depends on an orientation characterization of proper interval graphs. It is conceptually simple and does not use complex data structures. As a byproduct of the correctness proof of the algorithm, we also obtain a new proof of a characterization of proper interval graphs by forbidden subgraphs.