  We show that computing canonical representations for circular-arc (CA) graphs
reduces to computing certain subsets of vertices called flip sets. For a broad
class of CA graphs, which we call uniform, it suffices to compute a CA
representation to find such flip sets. As a consequence canonical
representations for uniform CA graphs can be obtained in polynomial-time. We
then investigate what kind of CA graphs pose a challenge to this approach. This
leads us to introduce the notion of restricted CA matrices and show that the
canonical representation problem for CA graphs is logspace-reducible to that of
restricted CA matrices. As a byproduct, we obtain the result that CA graphs
without induced 4-cycles can be canonized in logspace.
