| Abstract: | A graph G is a circular-arc graph if it is the intersectiongraph of a set of arcs on a circle. That is, there is one arc foreach vertex of G, and two vertices are adjacent in G if and only if thecorresponding arcs intersect. We give a linear-time algorithmfor recognizing this class of graphs. When G is a member ofthe class, the algorithm gives a certificate in the form ofa set of arcs that realize it. |
