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 adv antage of the fact that (among connected graphs) proper circular-arc g raphs are precisely the graphs orientable as local tournaments, and we use a new characterization of local tournaments. The algorithm depend s 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 gra phs. It is conceptually simple and does not use complex data structure s. As a byproduct of the correctness proof of the algorithm, we also o btain a new proof of a characterization of proper interval graphs by f orbidden subgraphs.