  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 outputs a certificate, along with its answer (be
it positive or negative), where the certificate can be used to easily justify
the given answer. While the recognition of circular-arc graphs has been known
to be polynomial since the 1980s, no polynomial-time certifying recognition
algorithm is known to date, despite such algorithms being found for many
subclasses of circular-arc graphs. This is largely due to the fact that a
forbidden structure characterization of circular-arc graphs is not known, even
though the problem has been intensely studied since the seminal work of Klee in
the 1960s.
  In this contribution, we settle this problem. We present the first forbidden
structure characterization of circular-arc graphs. Our obstruction has the form
of mutually avoiding walks in the graph. It naturally extends a similar
obstruction that characterizes interval graphs. As a consequence, we give the
first polynomial-time certifying algorithm for the recognition of circular-arc
graphs.
