An Efficient Test for Circular-Arc Graphs
Alan C. Tucker · SIAM Journal on Computing · 1980
An undirected graph G is called a circular-arc graph if there exists a family of arcs on a circle and a 1–1 correspondence between vertices and arcs such that two distinct vertices are adjacent if and only if the corresponding arcs overlap. Such a family is called a circular-arc model for G. In this paper we present an $O(n)^3 $-step algorithm for testing whether an n-vertex graph is a circular-arc graph, and if it is, constructing a circular-arc model. Unfortunately the algorithm, its proof, and its efficient implementation are all quite involved.