Forbidden structure characterization of circular-arc graphs and a certifying recognition algorithm

Mathew Francis, Pavol Hell, Juraj Stacho

A circular-arc graph is the intersection graph of arcs of a circle. It is a well-studied graph model with numerous natural applications. A certifying algorithm is an algorithm that…