{'fraction_non_alphanumeric': 0.04494595318920851, 'fraction_numerical': 0.004846346256923352, 'mean_word_length': 3.6856948514022605, 'pattern_counts': {'":': 15, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 17, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Canonical Representations for Circular-Arc Graphs Using Flip Sets

We show how to find canonical representations for circular-arc (CA) graphs by computing certain subsets of vertices called flip sets. A flip set enables one to convert a CA graph into an interval matrix in a reversible way. Since canonical representations for interval matrices can be computed in logspace this essentially means that the problem of finding canonical representations for CA graphs is logspace-reducible to computing 'canonical' flip sets. By applying this reduction we reveal that the canonical representation problem for a broad class of CA graphs reduces to the representation problem. We call this class uniform CA graphs. As a consequences canonical representations for uniform CA graphs can be obtained in polynomial time and the isomorphism problem for CA graphs is reducible to that of non-uniform CA graphs. Our main result is a logspace reduction from the canonical representation problem for CA graphs to the canonical representation problem for vertex-colored restricted CA matrices. Restricted CA matrices can be seen as slight generalization of non-uniform CA graphs. The class of restricted CA matrices has a very particular and easy to understand yet non-trivial structure which makes it suitable for combinatorial analysis. As a byproduct we obtain the result that canonical representations for CA graphs without induced 4-cycles can be computed in logspace.


Introduction
We consider an arc to be a connected set of points on the unit circle. A CA graph is a graph whose vertices can be assigned arcs such that two vertices are adjacent iff their corresponding arcs intersect. More formally, given a graph G we call it a CA graph if there exists a function ρ which maps every vertex u of G to an arc ρ(u) such that u and v are adjacent iff their arcs ρ(u) and ρ(v) have non-empty intersection. We call such a mapping ρ a CA representation of G. CA graphs are a form of geometrical intersection graphs. Let X be a family of sets over some ground set. Any subset Y of X defines a graph G Y which has Y as its vertex set and two vertices are adjacent if they have non-empty intersection. The graph G Y is called intersection graph of Y . We say a (finite) graph G is an intersection graph of X if it is isomorphic to the intersection graph of Y for some Y ⊆ X . In this language CA graphs are intersection graphs of arcs. The intersection graphs of intervals on the real line are called interval graphs. In this sense any set of geometrical objects defines a (geometrical intersection) graph class. CA graphs are a generalization of interval graphs since every set of intervals on the real line can be 'bent' into arcs while preserving the intersection relation. Therefore every interval graph is a CA graph.
Being a generalization of interval graphs-the archetype of geometrical intersection graphs-CA graphs are quite prominent as well and have been known since 1964 according to [1]. Since then structural properties and algorithmic problems for this class have been thoroughly investigated with [5] and [16] being two of the earliest works in this regard. In particular, finding characterizations of CA graphs and constructing a CA representation for a given CA graph have received a great deal of attention. Remarkably, finding a forbidden induced subgraph characterization of CA graphs is still an open problem. See [12] for a survey on this line of research and [1] for one of the most recent results in that direction. It should also be mentioned that CA graphs are of practical relevance with applications arising in disciplines such as genetics and operations research. An explanation of the connection between genetics and interval graphs in layman's terms can be found in [17]. For a specialized account on this connection emphasizing circularity see [15]. An example of how CA graphs can be used to model the problem of phasing traffic lights is given in [6].
In this work we consider the canonical representation problem for CA graphs. The representation problem for CA graphs is as follows. Given a CA graph G as input we want to output a CA representation ρ G of G. The canonical variant of this problem imposes the additional requirement that for every pair of isomorphic CA graphs G and H their representations ρ G and ρ H should have identical underlying sets of arcs, Notice that solving the representation problem for CA graphs implies solving the recognition problem for CA graphs, i.e. the question given a graph G is it a CA graph. Likewise, solving the canonical representation problem for CA graphs implies solving the isomorphism problem for CA graphs, i.e. deciding whether two given CA graphs are isomorphic.
Consider the following generalization of interval graphs: 2-interval graphs are intersection graphs of two intervals on the real line. It is easy to see that this class contains CA graphs because given a set of arcs one can cut the circle at some point and straighten the arcs. The arcs which are cut can be modeled as two intervals. It is interesting to note that the isomorphism problem for interval graphs is logspace-complete [9] while the one for 2-interval graphs is already GI-complete (because every line graph is a 2-interval graph) and CA graphs lie inbetween these two classes.
While a polynomial time algorithm for deciding isomorphism of interval graphs is known since 1976 due to Booth and Lueker this question still remains open for CA graphs. There have been two claimed polynomial time algorithms for deciding isomorphism of CA graphs in [18] and [7] which were shown to be incorrect in [4] and [3] respectively. For the subclass of interval graphs a linear-time algorithm for isomorphism has been described in [13]. A more recent result is that canonical interval representations for interval graphs can be computed in logspace and that this is optimal in the sense that recognition and deciding isomorphism for interval graphs is logspace-complete [9]. These two hardness results also carry over to the class of CA graphs. Furthermore, the isomorphism problem for the subclass of proper CA graphs [11] and Helly CA graphs [10] have been shown to be decidable in logspace. In fact, it is also shown how to obtain canonical representations for these classes in logspace.
A preliminary version of this work appeared in [2]. Our results show that the method used in [10] to obtain canonical representation for Helly CA graphs is applicable to CA graphs in general. First, we generalize their argument showing that in order to obtain canonical representations for CA graphs it suffices to compute certain subsets of vertices called flip sets in an isomorphism-invariant manner. Then we apply this argument to show that for a large subclass of CA graphs, namely uniform CA graphs, this immediately leads to a polynomial time algorithm. Uniform CA graphs are a superset of Helly CA graphs. By carefully analyzing non-uniform CA graphs we prove that the canonical representation problem for CA graphs is logspace-reducible to the canonical representation problem for restricted CA matrices. These matrices can be regarded as slight generalization of non-uniform CA graphs. At the end, we show how to apply the flip set approach to restricted CA matrices. This leads to a very specific question about how certain vertices in such restricted CA matrices can be represented. A consequence of our considerations is that canonical representations for CA graphs which do not contain induced 4-cycles can be computed in logspace. This is non-trivial because the isomorphism problem for graphs without induced 4-cycles is GI-complete.
The paper is organized as follows. In the third section we formalize the idea of computing invariant flip sets in order to obtain canonical representations for CA graphs. This leads to the definition of invariant flip set functions. In the fourth section we investigate for what CA graphs a particular invariant flip set function is easy to compute. This leads to the class of uniform CA graphs. We also show that this class enjoys an alternative characterization in terms of whether certain triangles in a CA graph have an unambiguous representation. The main result of this section is that the canonical representation problem for uniform CA graphs is logspace-equivalent to what we call non-Helly triangle representability problem. In the fifth section we consider the structure of non-uniform CA graphs and introduce restricted CA matrices. The idea behind restricted CA matrices is that they capture the 'global structure' of non-uniform CA graphs. We prove that the canonical representation problem for CA graphs is logspace-reducible to the canonical representation problem for (vertex-colored) restricted CA matrices. In the sixth section we show how the flip set approach can be used to find canonical representations for (vertex-colored) restricted CA matrices. such that A u,v = B π(u),π(v) for all u, v ∈ V ; π is called an isomorphism and if A = B then π is called an automorphism. Let τ be a bijection which maps the vertices of matrix A to some set V . We write τ (A) to denote the matrix obtained after relabeling the vertices of A according to τ , i.e. (τ (A)) τ (u),τ (v) = A u,v for all u, v ∈ V (A). We call τ a relabeling of A. Notice that a bijection π :

Preliminaries
We consider graphs as special case of binary square matrices. Additionally, we only consider undirected graphs without self-loops. A graph class C is a set of graphs which is closed under isomorphism, i.e. if G ∈ C and H ∼ = G then H ∈ C. We define the graph isomorphism problem for a graph class C such that the input is a pair of graphs (G, H) and one has to decide whether G and H are isomorphic whenever G, H ∈ C, otherwise the output can be arbitrary. The recognition problem for a graph class C asks whether an input graph G belongs to C.
The following definitions are with respect to a graph G. Throughout the paper it will be always clear from context with respect to what graph these expressions are to be interpreted.
For a vertex v we define its open neighborhood N (v) as the set of vertices which are adjacent to v and its closed neighborhood . A twin class is an inclusion-maximal set of vertices X such that for all u, v ∈ X it holds that u and v are twins. For two subsets of vertices S, S with S ⊆ S we define the exclusive neighborhood N S (S ) as all vertices v ∈ V (G) \ S such that v is connected to all vertices in S and to none in S \ S . Let A be a square matrix with entries from a set E. For a vertex v of A and e ∈ E we define N e (v) = {u ∈ V | A v,u = e}.

Logspace Transducers and Reductions
Throughout the paper deterministic Turing machines are assumed as default model of computation. A logspace transducer is a deterministic Turing machine M with a read-only input tape, a work tape and a write-only output tape. To write onto the output tape M has a designated state called output state with the following semantic. If M enters the output state then the symbol in the current cell of the work tape is written to the current cell of the output tape and the head on the output tape is moved one cell to the right. Other than that, M cannot write or move the head on the output tape. This means as soon as something is written to the output tape it cannot be modified afterwards. Let Σ and Γ be the input and work alphabet of M respectively. Then M computes a function f M : We call f logspace-computable if there exists a logspace transducer M which computes f . The class of logspace-computable functions is closed under composition. Given two finite sets A, B and a function f : A * → B * we say that the length of f is polynomially bounded if |f (x)| is polynomially bounded by |x|. Notice that only functions whose length is polynomially bounded can be logspace-computable since the runtime of a logspace transducer is polynomially bounded. A language L ⊆ Σ * is in logspace if its characteristic function is logspace-computable.
Next, we specify what it means for a logspace transducer M to have an oracle. Let ∆ be a finite, non-empty set and f : ∆ * → ∆ * is a function whose length is polynomially bounded. Let M be a logspace transducer with work alphabet Γ and ∆ ⊆ Γ. We say M has oracle access to f if M has two additional tapes: a write-only tape named query tape and a read-only tape named answer tape. The query tape essentially behaves like the output tape in the sense that there is a designated state which allows M to write onto it and once written to it the content cannot be modified. The oracle mechanism works as follows. As soon as M enters a designated state which triggers the oracle the current word x from the query tape is read and then the contents of the query and answer tape are erased. Then the oracle writes f (x) to the answer tape.
Given two functions f and g we say f is logspace-reducible to g if there exists a logspace transducer M with oracle access to g which computes f . Similarly, given three functions f, g, h we say f is logspace-reducible to g and h if there exists a logspace transducer M with oracle access to g and h which computes f . If f is logspace-reducible to g and g is logspace-computable then so is f . This closure holds because if g is logspace-computable then a logspace transducer M g which computes g can be used to replace the oracle queries. Even though it is in general not possible to write the whole answer x of an oracle query to the work tape as it might be too long it suffices to compute single bits of x 'on the fly'.

Isomorphism-Invariance
The following notions apply to square matrices as well. Let f be a function which maps labeled graphs (adjacency matrices) to some target set D such as the natural numbers. Then f is called a graph invariant for a graph class C if f (G) = f (H) whenever G and H are isomorphic and G, H ∈ C. If the other direction holds as well, i.e. G and H are isomorphic whenever f (G) = f (H) and G, H ∈ C then f is called a complete graph invariant for C.
Additionally, if f (G) ∼ = G holds for all G ∈ C then f is a canonical form for C. Let F be a function which maps a graph to a relabeling, i.e.
Using the concept of orbits for vertex sets a local variant of graph invariants can be defined. Given two graphs G, H and two subsets of vertices X ⊆ V (G), Y ⊆ V (H) we say X and Y are in the same orbit, in symbols X ∼ orb Y , if there exists an isomorphism π from G to H such that π(X) = Y . Notice that ∼ orb is an equivalence relation. Let f be a function which maps graphs and a subset of vertices to some target set D, i.e. f (G, X) ∈ D for X ⊆ V (G). We say f is a vertex set invariant for the graph class Let us call a function f which maps graphs to a subset of subsets of their vertices, i.e. f (G) ⊆ P(G), a vertex set selector. The characteristic function χ f of a vertex set selector f is defined as χ f (G, X) = 1 ⇔ X ∈ f (G). We say a vertex set selector f is invariant for a graph class C if its characteristic function χ f is a vertex set invariant for C. We call f globally invariant if χ f is a vertex set invariant for all graphs. We say a vertex set selector f is label-independent for a graph class C if for all isomorphic graphs G, H ∈ C and all isomorphisms π from G to H it holds that f (H) = {π(X) | X ∈ f (G)}. Notice, a vertex set selector f is label-independent for C iff f is invariant for C. Intuitively, a vertex set selector f is invariant for C if a graph G ∈ C can be arbitrarily relabeled and f still returns the 'same' vertex sets as before. To show that a vertex set selector f is invariant on C it suffices to show that for all graphs G, H ∈ C and isomorphisms π from G to H it holds that π(X) is in f (H) whenever X is in f (G) because the other direction is implied by the symmetry of the statement.

Circular-Arc Graphs and Representations
A CA model is a set of arcs A = {A 1 , . . . , A n } on the circle. Let p = p be two points on the circle. Then the arc A specified by [p, p ] is given by the part of the circle that is traversed when starting from p going in clockwise direction until p is reached. We say that p is the left and p the right endpoint of A and write l(·), r(·) to denote the left and right endpoint of an arc in general. If A = [p, p ] then the arc obtained by swapping the endpoints A = [p , p] covers exactly the opposite part of the circle plus the endpoints. We say A is obtained by When considering a CA model with respect to its intersection structure only the relative position of the endpoints to each other matter. All endpoints can w.l.o.g. be assumed to be pairwise different and no arc covers the full circle. Therefore a CA model A with n arcs can be described as a unique string as follows. Pick an arbitrary arc A ∈ A and relabel the arcs with 1, . . . , n in order of appearance of their left endpoints when traversing the circle clockwise starting from the left endpoint of A. Then write down the endpoints in order of appearance when traversing the circle clockwise starting from the left endpoint of the first arc(A). Do this for every arc and pick the lexicographically smallest resulting string as representation for A. For example, the smallest such string for the CA model in Figure 1 would result from choosing . In the following we identify A with its string representation. Therefore we assume two CA models to be equal if their string representations are identical.
Let G be a graph and ρ = (A, f ) consists of a CA model A and a bijective mapping f from the vertices of G to the arcs in A. Then ρ is called a CA representation of G if for all We say a CA model A has a hole if there exists a point on the circle which isn't contained by any arc in A. Every such CA model can be understood as interval model (a set of intervals on the real line) by straightening the arcs. Conversely, every interval model can be seen as CA model by bending the intervals. Therefore a graph is an interval graph iff it admits a CA representation with a hole. A CA graph G is called Helly (HCA graph) if it has a CA representation ρ such that for all inclusion-maximal cliques C in G it holds that the overall intersection of C in ρ is non-empty, i.e. v∈C ρ(v) = ∅. Every interval model has the Helly property and therefore every interval graph is a Helly CA graph.
The intersection type of two circular arcs A and B can be one of the following five types: Using these types we can associate a matrix with every CA model. An intersection matrix is a square matrix with entries {cc, cd, cs, di, ov}. Given a CA model A we define its intersection matrix µ A such that (µ A ) A,B ∈ {cc, cd, cs, di, ov} reflects the intersection type of the arcs A = B ∈ A. An intersection matrix µ is called a CA (interval) matrix if it is the intersection matrix of some CA model (with a hole). See Figure 2 for an example of a CA model and the CA matrix which it induces. Given an intersection matrix µ and two distinct vertices u, v of µ we sometimes write u α v instead of µ u,v = α if µ is clear from the context. Also, we sometimes talk about an intersection matrix µ as if it were a graph. In that case we consider two vertices u, v of µ to be adjacent if they do not have a di-entry in µ. When trying to construct a CA representation for a CA graph G it is clear that whenever two vertices are non-adjacent their corresponding arcs must be disjoint in every CA representation of G. For two adjacent vertices the intersection type of their corresponding arcs might depend on the particular CA representation of G that one considers. Hsu has shown that one can remove this ambiguity using the following argument [7]. We adopt the notation of [10]. Definition 2.1. For a graph G we define its neighborhood matrix λ G which is an intersection matrix as Let µ be an intersection matrix over the vertex set V and ρ = (A, f ) where A is a CA model and f is a bijective mapping from V to A. We say ρ is a CA representation for µ if f is an isomorphism from µ to the intersection matrix µ A of A. We denote the set of such CA representations for µ with N (µ). The representation problem for CA matrices is to compute a CA representation for a given CA matrix µ. The canonical representation problem for CA matrices is defined analogously to the canonical representation problem for CA graphs. We say ρ is a normalized CA representation for a graph G if ρ is a CA representation for the neighborhood matrix λ G of G. An example of a normalized representation can be seen in Figure 3. Let us denote the set of all normalized CA representations for G with N (G) = N (λ G ).

Lemma 2.2 (Corollary 2.3. [7]
). Every twin-free CA graph G without a universal vertex has a normalized CA representation, that is N (G) = ∅. Lemma 2.3. The (canonical) representation problem for CA graphs is logspace reducible to the (canonical) representation problem for twin-free CA graphs without a universal vertex.
Proof. First, we argue that the representation problem for CA graphs is logspace reducible to the representation problem for CA graphs without a universal vertex. For a graph G let G denote the graph G after removing all universal vertices from it. Notice that G is a CA graph iff G is a CA graph. Additionally, let k denote the number of universal vertices in G (if k = 0 then G = G ). Both G and k are logspace-computable. Let ρ be the CA representation of G that is given by the oracle. Then add k arcs which cover the whole circle to ρ to obtain a CA representation for G.
The representation problem for CA graphs without a universal vertex can be reduced to the representation problem for twin-free CA graphs without a universal vertex as follows. Given a graph G without a universal vertex compute a twin-free version of it as follows. Let X 1 , . . . , X k be the set of twin classes of G and v i denotes the lexicographically smallest vertex in X i for i ∈ [k]. Notice that the sets X 1 , . . . , X k partition V (G). We call the induced subgraph of G on vertex set {v 1 , . . . , v k } G . It holds that G is twin-free and logspacecomputable. Let ρ be the representation of G given by the oracle. A representation ρ for G is then given by The same argument also works for the canonical variant of the problem.
Therefore for our purposes it suffices to consider only twin-free graphs without universal vertices.
Proviso. From this point on we assume every graph to be twin-free and without a universal vertex unless explicitly stated otherwise. As a consequence we view CA graphs as a subset of CA matrices in the sense that the neighborhood matrix of every CA graph is a CA matrix.

Flips in Intersection Matrices
McConnell observed that the operation of flipping arcs in CA models has a counterpart in intersection matrices. He called this counterpart operation algebraic flips. Consider that for two arcs A, B with intersection type α ∈ {cc, cd, cs, di, ov} the intersection type of A and B is solely determined by α. More precisely, it holds that A α B where α = Z 10 (α) and Z 10 is defined in Table 1. Similarly, the intersection type of A and B is given by Z 01 (α). Using these functions Z ij we can define the operation of flipping a set of vertices in an intersection matrix.

Definition 2.4.
Given an intersection matrix µ with vertex set V and X ⊆ V . We define the intersection matrix µ (X) obtained after flipping the vertices X in µ as Since flipping the same set of arcs twice is an involution it follows that (µ (X) ) (X) = µ. cs di cc cd ov Z 10 cd cc di cs ov Z 11 di cs cd cc ov Definition 2.5. Given a set of vertices V , a set of arcs A and a function ρ : V → A. Then ρ (X) : V → A for X ⊆ V is defined as follows: Notice that flipping vertices in an intersection matrix is equivalent to flipping arcs in a CA representation in the following sense. Given an intersection matrix λ and a subset of its vertices X. It holds that ρ ∈ N (λ) ⇔ ρ (X) ∈ N (λ (X) ). The following statement shows that flipping is an isomorphism-invariant operation in the sense that flipping sets of vertices which are in the same orbit lead to isomorphic intersection matrices.

Lemma 2.6. Let λ and µ be intersection matrices and
"⇐": The same argument as for the other direction can be made by using the inverse functions Z −1 ij .

Flip Trick
In this section we generalize the idea used by Köbler, Kuhnert and Verbitsky in [10] to compute canonical representations for Helly CA graphs. They showed that finding canonical representations for Helly CA graphs can be reduced to finding canonical representations for vertex-colored interval matrices. We argue that the idea behind this reduction also works for CA matrices in general if certain subsets of vertices, which we call flip sets, can be computed invariantly. Recall that CA graphs can be seen as special case of CA matrices since the neighborhood matrix of every CA graph is a CA matrix but the converse does not hold, i.e. there exist CA matrices which are not expressible as the neighborhood matrix of a CA graph (for instance any CA matrix with only two vertices that are not disjoint). The key result here, which is used in the subsequent sections, is that finding canonical representations for CA matrices is logspace-reducible to the task of computing what we call an invariant flip set function.
McConnell showed that given a CA graph G with neighborhood matrix λ one can compute a set of vertices X of G such that λ (X) is an interval matrix. Then by computing an interval representation ρ for λ (X) and flipping back the arcs X in ρ one obtains a CA representation ρ X = ρ (X) for λ and therefore for G as well [14]. This method was extended in [10] in order to yield canonical representations for Helly CA graphs. In the following we give a brief high-level overview of this canonization argument. To reduce the canonical representation problem for CA matrices to the canonical representation problem for vertex-colored interval matrices we want to construct a reduction function r which maps CA matrices to vertex-colored interval matrices such that for all CA matrices λ, λ it holds that λ ∼ = λ iff r(λ) ∼ = r(λ ). Then a canonical form of a CA matrix λ is given by a canonical form of the vertex-colored interval matrix r(λ).
To convert a CA matrix λ into an interval matrix we need to find a certain subset of vertices X of λ such that λ (X) is an interval matrix. We call a subset of vertices with this property a flip set. McConnell has observed in [14] that every CA matrix λ has a flip set: given a representation ρ of λ and a point x on the circle let X denote the set of arcs in ρ that contain Then X must be a flip set as we will see.
Suppose that we have a function f which maps intersection matrices to a subset of their vertices, i.e. f (λ) ⊆ V (λ), and f has the following two properties: (1) f (λ) is a flip set whenever λ is a CA matrix and (2) f (λ) and f (λ ) are in the same orbit whenever λ and λ are isomorphic. Using the function f we can express the following reduction function r. For an intersection matrix λ and X ⊆ V (λ) let c X denote the coloring of the vertices of λ where c X (v) is red if v ∈ X and blue otherwise. Then r(λ) = (λ (X) , c X ) with X = f (λ) is a correct reduction function. The correctness is a consequence of the following two observations. First, if λ is a CA matrix then λ (X) is an interval matrix due to property (1) of f . Secondly, whenever we have two isomorphic CA matrices λ and µ it holds that f (λ) and f (µ) are isomorphic as well because we flip the 'same' vertices in λ and µ due to property (2) of f .
We will relax the two conditions that we require of a function like f and call such functions invariant flip set functions. Then we show how to obtain a canonical representation by using such an invariant flip set function. At the end of this section we state the invariant flip set function that was used in [10] to compute canonical representations for Helly CA graphs.
The concept of flip sets has already been implicitly defined and used in both [14] and [10]. They observed that λ (X) is an interval matrix whenever X is a flip set of a CA matrix λ. In fact, the other direction holds as well leading to the following characterization.

Lemma 3.2.
Let λ be a CA matrix and X is a subset of vertices of λ. It holds that X is a flip set iff λ (X) is an interval matrix.
Proof. "⇒": Let X be a flip set of λ. We show that λ (X) is an interval matrix. Let ρ ∈ N (λ) be a witnessing representation of the fact that X is a flip set, i.e. there exists a point x on the circle such that every arc ρ(v) with v ∈ X contains x and every arc ρ(v) with v / ∈ X does not contain x. Consider the representation ρ (X) ∈ N (λ (X) ). It holds that no arc There is an exception, however, if x is the endpoint of some arc ρ(u). In that case after flipping the arcs X the point x is still covered by an endpoint of u in the new representation. But if one considers the point x which is infinitesimally close to x and contained by ρ(u) then this point x is not covered by any arc after flipping X.
"⇐": Let X be a subset of vertices of λ such that λ (X) is an interval matrix. We show that X must be a flip set. Let ρ ∈ N (λ (X) ) be a CA representation of λ (X) containing a hole at point x on the circle. Such a representation must exist since λ (X) is an interval matrix. This means the arc ρ(v) does not contain the point x for every vertex v ∈ V (λ). Consider the representation ρ (X) ∈ N ((λ (X) ) (X) ) = N (λ). Then it can be checked that ρ (X) (v) contains the point x iff v is in X and therefore X is a flip set with respect to λ.
We already mentioned that the canonical representation problem for vertex-colored interval matrices can be solved in logspace due to [10]. However, since the theorem that we reference just states this result for uncolored interval matrices we shortly explain how to modify the proof to incorporate the coloring, which is a straightforward task for anyone familiar with the proof. Proof. In Theorem 5.5 of [10] it is stated that a canonical interval representation for an interval matrix can be found in logspace. To prove this they convert the input interval matrix λ into a colored tree T(λ) called ∆ tree which is a complete invariant for interval matrices. The leafs of this tree correspond to the vertices of λ. By appending the color of a vertex from our vertex-colored interval matrix λ to the existing color of its corresponding leave node in the colored ∆ tree T(λ) one obtains a complete invariant for vertex-colored interval matrices. Then by applying the same argument given in the proof of Theorem 5.5 one can also compute a canonical representation for a vertex-colored interval matrix using this slightly modified colored ∆ tree.

Fact 3.4. Let λ be an intersection matrix and X is a subset of vertices of λ. On input λ and X it can be decided in logspace whether X is a flip set.
Proof. To decide if X is a flip set it suffices to check whether λ (X) is an interval matrix due to Lemma 3.2. Notice that only intersection matrices which are CA matrices have flip sets. To find out whether λ (X) is an interval matrix we try to compute an interval representation for it, which can be done in logspace due to the previous Theorem 3. 3. It remains to verify that the outputted interval representation is in fact correct for λ (X) . This can be done by inspecting the relative position of the endpoints for each two vertices and verifying that they match the corresponding intersection type in λ (X) . Lemma 3.5. Given a CA matrix λ and a flip set X of λ a representation ρ X ∈ N (λ) can be computed in logspace.
Proof. For a CA matrix λ and a flip set X compute the matrix λ (X) . By Lemma 3.2 it follows that λ (X) is an interval matrix. By Theorem 3.3 we can compute a representation ρ ∈ N (λ (X) ) in logspace. Then the desired representation is given by ρ X = ρ (X) . It holds that ρ X is a normalized representation of λ since ρ (X) ∈ N ((λ (X) ) (X) ) and (λ (X) ) (X) = λ.
We can now give a formal definition of invariant flip set functions and show that being able to compute such a function for CA matrices implies that one can obtain canonical representations as well. In fact, we give a slightly more general definition which states what conditions an invariant flip set function must satisfy in order to 'work' (yield canonical representations) for a subclass of CA matrices. Recall that we are primarily interested in the subclass of CA matrices which occur as neighborhood matrix of some CA graph. Definition 3.6. Let C be a subclass of CA matrices and f is a vertex set selector. The function f is called an invariant flip set function for C if the following conditions hold: 1. For every λ ∈ C there exists an X ∈ f (λ) such that X is a flip set of λ 2. f is invariant for C Theorem 3.7. Let C be a subclass of CA matrices. The canonical representation problem for C is logspace-reducible to the problem of computing an invariant flip set function for C.
Proof. Let f be an invariant flip set function for a subclass C of CA matrices. To obtain a canonical representation of a CA matrix λ ∈ C we claim that a canonical labeling τ λ of λ can be computed in logspace using the invariant flip set function f as oracle. Then the canonical representation can be easily derived from the canonical labeling τ λ as follows. Compute the canonical form canon(λ) = τ λ (λ) of λ and choose the lexicographically smallest flip set X in f (canon(λ)). Using Lemma 3.5 we can compute a representation ρ X ∈ N (canon(λ)). A canonical representation ρ ∈ N (λ) is then given by Now, we show how to compute a canonical labeling τ λ for λ. For every flip set X ∈ f (λ) we associate it with the following colored interval matrix . Let canon(I X λ ) denote its canonical form and τ X is a canonical labeling with τ X (I X λ ) = canon(I X λ ), which both can be computed in logspace due to Theorem 3.3. LetX be a flip set in f (λ) such that canon(IX λ ) is lexicographically minimal, i.e. there exists no flip set X in f (λ) such that canon(I X λ ) is lexicographically smaller than canon(IX λ ). We output τX and claim that this is a canonical labeling of λ.
To prove this we will use the following statement ( ) which is a direct consequence of Lemma 2.6: for all CA matrices λ, µ ∈ C and flip sets X ∈ f (λ), Y ∈ f (µ) it holds that π is an isomorphism from λ to µ with π(X) = Y iff π is an isomorphism from I X λ to I Y µ . Consider two isomorphic CA matrices λ, µ ∈ C and letX ∈ f (λ),Ŷ ∈ f (µ) be the flip sets which lead to the alleged canonical labellings τX and τŶ of λ and µ respectively. It holds that canon(IX λ ) = canon(IŶ µ ). To see this consider the set of colored interval matrices I λ = I X λ | X is a flip set in f (λ) and I µ which is defined analogously. It holds that for every colored interval matrix in I λ there exists an isomorphic one in I µ and vice versa. Let I X λ be in I λ due to the flip set X ∈ f (λ). Since f is invariant for C it follows that there exists an Y ∈ f (µ) such that X and Y are in the same orbit. From the "⇒" direction of ( ) it follows that I X λ and I Y µ are isomorphic and since Y ∈ f (µ) it holds that I Y µ ∈ I µ . Therefore for every colored interval matrix in I λ there is an isomorphic counterpart in I µ . The other direction holds for the same reason. From that we can deduce that canon(IX λ ) = canon(IŶ µ ) since they both are the lexicographically smallest element in {canon(I) | I ∈ I λ } = {canon(I) | I ∈ I µ }.
We can now show that is an isomorphism from λ to µ and therefore τX and τŶ are canonical labellings. Recall that π is an isomorphism from IX λ to Therefore π is an isomorphism from IX λ to IŶ µ . Due to the "⇐" direction of ( ) it follows that π is an isomorphism from λ to µ as well.
In the next section we will see that for a broad class of CA graphs C the problem of computing an invariant flip set function naturally reduces to the problem of computing a representation for C. Let C be the set of CA graphs which are not in C. One might be misled into thinking that if invariant flip sets functions for both C and C can be computed then this directly implies solving the canonical representation problem for CA graphs. Alas, this is not the case. Clearly, if we can recognize the graph class C (or C) then a simple case distinction to decide which invariant flip set function to use solves the problem. However, there is an alternative solution which might possibly be easier than solving the recognition problem for C. Concretely, it suffices if one of the two invariant flip set functions is globally invariant as the following fact shows. Fact 3.8. Let C and C be subclasses of CA matrices such that C ⊆ C. There is a logspace reduction from the canonical representation problem for C to the canonical representation problem for C \ C and the problem of computing a globally invariant flip set function for C .
Proof. Let f be the globally invariant flip set function for C which is computed by one of the two oracles. Let C be the set of matrices such that λ ∈ C iff f (λ) contains a flip set. It holds that f is an invariant flip set function for C as well since it satisfies the first condition of Definition 3.6 by definition and the second directly follows from the fact that f is globally invariant. Additionally, it holds that C is closed under isomorphism and C is a subset of C . Now, the reduction works as follows. On input λ compute f (λ). If f (λ) contains at least one flip set then we know that G is in C and therefore we can apply Theorem 3.7 to obtain a canonical representation for λ. If f (λ) does not contain a flip set then we know that λ is not in C and therefore also not in C since C is a subset of C . In that case we can use the other oracle to compute a canonical representation for λ.
Regarding the computational complexity of this reduction each step but the computation of f (λ) and the computation of a canonical representation for λ if λ / ∈ C clearly works in logspace.
To conclude this section we restate the invariant flip set function that was used in [10] to compute canonical representations for Helly CA graphs. In fact, this function is even globally invariant and therefore the canonical representation problem for CA graphs is reducible to the canonical representation problem for non-Helly CA graphs due to the previous Fact 3.8.

globally invariant flip set function for Helly CA graphs.
Proof. In a Helly CA graph G every inclusion-maximal clique C of G is a flip set. To see this let ρ be a representation of G with the Helly property. Since C is a clique this means every pair of arcs ρ(u) and ρ(v) with u, v ∈ C intersects. By the Helly property it follows that the overall intersection v∈C ρ(v) is non-empty. This means there exists a point x on the circle such that every arc ρ(v) with v ∈ C contains x. Assume there exists a vertex w ∈ V (G) \ C such that ρ(w) contains x. This means w must be adjacent to every vertex in C, which contradicts that C is inclusion-maximal. Therefore C is a flip set.
In [10,Thm. 3.2] it is shown that every Helly CA graph contains at least one inclusionmaximal clique which can be expressed as the common neighborhood of two vertices. Therefore f (G) returns at least one flip set for every Helly CA graph G. To prove that f is globally invariant we show that for every pair of isomorphic graphs G and H with disjoint vertex sets and all isomorphisms π from G to H it holds that since π is an isomorphism from G to H. Therefore π(X) is in f (H) since it can be expressed as the intersection of the closed neighborhoods of π(u) and π(v).

Uniform Circular-Arc Graphs
We introduce the class of uniform CA graphs for which computing a particular invariant flip set function naturally reduces to computing a representation. As a consequence canonical representations for this subclass can be computed in polynomial time. While the initial definition of uniformity makes it apparent why it suffices to find an arbitrary representation in order to obtain a canonical one it is rather impractical when trying to understand what constitutes a uniform CA graph. However, we provide a more pleasant characterization of uniform CA graphs in terms of how certain triangles in a CA graph can be represented. This alternative characterization also readily reveals that every Helly CA graph is uniform. Additionally, we show that the canonical representation problem for uniform CA graphs is logspace-equivalent to what we call the non-Helly triangle representability problem. This problem is: given a CA graph G and a set T of three pairwise overlapping vertices as input does there exist a representation ρ of G such that T covers the whole circle in ρ.
The following kind of flip set will lead us to uniform CA graphs when trying to compute canonical representations. Given a CA matrix λ recall that X is a flip set of λ if there exists a representation ρ ∈ N (λ) and a point x on the circle such that x ∈ ρ(v) iff v ∈ X for all vertices v of λ. We restrict this by saying that x is not allowed to be an arbitrary point on the circle but instead has to be one of the endpoints in ρ. Consider the following task: given a CA graph G and a vertex u find a u-flip set of G. Clearly, no vertex v which is disjoint from u or contained by u belongs to X since in every representation the arc of v does not contain any of the two endpoints of the arc of u. Similarly, if a vertex v contains u or forms a circle cover with u then in every representation the arc of v contains both endpoints of u and therefore must be included in X. See Figure 4 for a schematic overview.
It remains to decide for the set of vertices N ov (u) that overlap with u whether they should be included in X. Recall that a vertex v which overlaps with u contains exactly one of the endpoints of u in any representation. Let x, y be two vertices that overlap with u. We say x and y overlap from the same side with u in ρ if ρ(x) and ρ(y) contain the same endpoint of ρ(u). Evidently, this is an equivalence relation with respect to v and ρ which partitions N ov (u) into two parts, namely the part which contains the left endpoint and the one which contains the right endpoint. If X is a u-flip set then X ∩ N ov (u) must be an equivalence class of the 'overlap from the same side with u in ρ'-relation for some ρ ∈ N (G).

Definition 4.2.
For a CA matrix λ and a vertex u of λ we say a partition Y of N ov (u) into two parts is a u-ov-partition if there exists a representation ρ ∈ N (λ) such that two vertices x, y ∈ N ov (u) are in the same part of Y iff ρ(x) and ρ(y) overlap from the same side with ρ(u). We call a partition Y of a subset of vertices of λ into two parts an ov-partition if it is an u-ov-partition for some u ∈ V (λ). In general, for a vertex u of a CA graph G there can be multiple u-ov-partitions. In fact, there are instances with exponentially many u-ov-partitions with respect to |N ov (u)|. A trivial way of obtaining at least one u-ov-partition for every vertex u of a CA graph G is to compute an arbitrary representation ρ ∈ N (G). But the ov-partitions obtains by this method are not invariant and thus do not yield canonical representations. However, there is a subclass of CA graphs where computing an arbitrary representation yields invariant ov-partitions nonetheless. Namely, it is the class of CA graphs where for every vertex u there exists exactly one u-ov-partition.
Proof. To prove this statement we need to show that for every uniform CA graph G there exists at least one set in F uniform (G) which is a flip set and that this function is invariant for uniform CA graphs.
For the first part we argue that the even stronger claim holds that every set in Given a representation ρ ∈ N (G) let x u,i be the endpoint of ρ(u) which is contained by every arc ρ(v) with v ∈ P u,i . It holds that the point x u,i is contained by every arc that contains or forms a circle cover with u. Similarly, no arc that is disjoint from u, contained by u or overlaps from the other side with u (P u,j with j = i) contains the point x u,i . Therefore the point x u,i is exactly contained by the arcs of X u,i w.r.t. ρ; see Figure 4 for an overview.
For the second part we need to show that F uniform is invariant for uniform CA graphs. Consider two isomorphic uniform CA graphs G, H with disjoint vertex sets and X ⊆ V (G), Y ⊆ V (H) such that X and Y are in the same orbit and X ∈ F uniform (G). We need to show that Y ∈ F uniform (H). Let π be an isomorphism from G to H such that π(X) = Y . Since X ∈ F uniform (G) there exists a u ∈ V (G) and i ∈ {1, 2} such that ). Then it remains to to argue that Y = P u ,j for some j ∈ {1, 2}. Given a representation ρ G ∈ N (G) we know that {ρ G (v) | v ∈ P u,i } is an inclusion-maximal set of arcs that overlap from the same side with ρ G (u). Observe that π(P u,i ) = Y due to the fact that π is a bijective mapping between X and Y and π(X) \ π(P u, i } must be an inclusion-maximal set of arcs that overlap from the same side with ρ H (u ) = ρ G (u). This concludes that Y = P u ,j for some j ∈ {1, 2}.
Notice, that the function F uniform is undefined for non-uniform CA graphs since the sets P u,1 and P u,2 are not well-defined in that context. Proof. The canonical representation problem for uniform CA graphs is logspace-reducible to the representation problem for uniform CA graphs. The claim then follows from the fact that representations for CA graphs can be computed in polynomial time, see for instance [14].
Let G be a uniform CA graph. To compute the invariant flip set function F uniform (G) we need for every vertex u of G the set of neighbors of u that form a circle cover or contain u and the two parts P u,1 , P u,2 of its u-ov-partition. The sets N cc (u) and N cd (u) can be obtained by computing the neighborhood matrix. To get P u,1 and P u,2 it suffices to compute an arbitrary representation ρ ∈ N (G) using the oracle and then extract the u-ov-partition that it induces since every representation must lead to the same u-ov-partition in a uniform CA graph.
Considering that our definition of uniform CA graphs arose from the desire to compute invariant u-flip sets one might expect that these graphs are only a small special case of CA graphs. Surprisingly, quite the opposite is the case as we will see. We give an alternative definition of uniform CA graphs which gives a better intuition as to why many CA graphs are uniform. Definition 4.6. Let λ be a CA matrix. An ov-triangle T of λ is a set of three vertices that overlap pairwise, i.e. for all u = v in T it holds that u ov v. An ov-triangle T is representable as non-Helly triangle (interval triangle) if there exists a representation ρ ∈ N (λ) such that the set of arcs {ρ(x) | x ∈ T } does (not) cover the whole circle. Let T NHT (λ) and T IT (λ) denote the sets of ov-triangles representable as non-Helly triangles and interval triangles respectively.
This definition also applies to CA graphs via their neighborhood matrix, i.e. T IT (G) = T IT (λ) and T NHT (G) = T NHT (λ) where λ is the neighborhood matrix of G.
See Figure 6 for an example where the vertices u, x, z are represented as non-Helly triangle on the left and interval triangle on the right.
Recall that a set of arcs which intersect pairwise but have overall empty intersection is called non-Helly. Since three pairwise overlapping arcs that cover the whole circle have overall empty intersection we call such a set a non-Helly triangle. In fact, one can verify that this is the only non-Helly arrangement of three arcs. A complete list of inclusion-minimal non-Helly CA models can be found in [8, Corrollary 3.1].

Theorem 4.7. A CA graph
Proof. "⇒": Assume there exists a uniform CA graph G with T IT (G) ∩ T NHT (G) = ∅. Let T be an ov-triangle in T IT (G) ∩ T NHT (G) and T = {x, y, z}. This means there exist two representations ρ I , ρ N ∈ N (G) such that T is represented as interval triangle in ρ I and as non-Helly triangle in ρ N . We assume w.l.o.g. that ρ I (y) ⊂ ρ I (x) ∪ ρ I (z), i.e. y is placed in-between x and z in ρ I . This means y and z must be in the same part of the unique x-ov-partition P x . However, y and z do not contain the same endpoint of x in the representation ρ N , which contradicts that G is uniform. "⇐": Assume there exists a CA graph G with T IT (G) ∩ T NHT (G) = ∅ that is not uniform. This means there exist a vertex u, two vertices x, y ∈ N ov (u) and two representations ρ, ρ ∈ N (G) such that x and y overlap from the same side with u in ρ but not in ρ . This implies that x and y must overlap and therefore T = {u, x, y} is an ov-triangle. Notice that T must be represented as interval triangle in ρ because x and y both contain the same endpoint of u. It holds that T is represented as interval triangle in ρ as well since otherwise T ∈ T IT (G) ∩ T NHT (G). Also, we assume w.l.o.g. that ρ(y) ⊂ ρ(x) ∪ ρ(u). Since u and y overlap it holds that N . For a vertex z ∈ N [u] \ N [y] to intersect with both u and x it is necessary that z overlaps with u and x due to the representation ρ. It follows that {u, x, z} is represented as non-Helly triangle in ρ. Additionally, {u, x, z} must be represented as interval triangle in ρ and therefore T IT (G) ∩ T NHT (G) = ∅, contradiction. See Figure 6 for a schematic overview of ρ and ρ .
Observe that if an ov-triangle T of G is representable as non-Helly triangle then this implies that T must have certain structural properties in G. For example, every vertex of G must be adjacent to at least one of the vertices in T since T covers the whole circle in some representation. Similarly, if T is representable as interval triangle this also implies such structural properties. For instance, there must be an x ∈ T such that every vertex that is adjacent to x must also be adjacent to at least one other vertex in T . If an ov-triangle is representable as both non-Helly triangle and interval triangle then it must satisfy all of these structural properties at once. As a consequence such an ov-triangle must have a very particular structure which extends to the whole graph as we will see in the next section.
This alternative characterization can be interpreted as the fact that for uniform CA graphs being a non-Helly triangle is a property which is determined by the graph itself rather than a particular representation of it.
Indeed, the class of uniform CA graphs can be even defined without invoking the concepts of normalized representations and neighborhood matrices. A CA graph G is uniform iff every overlapping triangle T of G covers the circle in every representation of G whenever T covers the circle in one representation of G.
Proof. The notion of necessarily overlap that we just defined coincides with the one from the neighborhood matrix. This means given a CA graph G and u, v ∈ V (G) it holds that u and v necessarily overlap iff u ov v. Therefore an overlapping triangle is the same as an ov-triangle. Notice, that an overlapping triangle T covers the circle in a representation ρ this is equivalent to saying that T is represented a non-Helly triangle in ρ by definition. Hence the "⇐"-direction of the characterization trivially holds. For the "⇒"-direction assume that G is a uniform CA graph but there exists an overlapping triangle T of G and two representations ρ and ρ such that T is represented as non-Helly triangle in ρ and as interval triangle in ρ . One can convert ρ and ρ into normalized representations without affecting how T is represented. Therefore T ∈ T NHT (G) ∩ T IT (G), contradiction.
Recall that a CA graph is Helly if it has a Helly CA representation. In [8,Theorem 4.1] it is shown that every 'stable' representation of a Helly CA graph is Helly. Since every normalized representation has the 'stable' property it follows that a CA graph is Helly iff every normalized representation of it is Helly. As a consequence Helly CA graphs are a subset of uniform ones. Proof. The containment follows from the stronger claim that T NHT (G) = ∅ for every Helly CA graph G. Assume there exists a Helly CA graph with an ov-triangle T that is representable as non-Helly triangle in some normalized representation ρ of G. Then ρ is not Helly which contradicts that every normalized representation of a Helly CA graphs should be Helly as well. An example of a uniform CA graph which is not Helly is the net graph .
A natural question to consider is the computational complexity of deciding whether a given ov-triangle is representable as non-Helly triangle or interval triangle. In the case of uniform CA graphs these two problems are complementary, i.e. an ov-triangle T is in T NHT (G) iff T is not in T IT (G). Interestingly, solving either of these two problems for uniform CA graphs is logspace-equivalent to computing a canonical representation for uniform CA graphs.
Definition 4.10. The non-Helly triangle representability problem for a subclass of CA graphs C is defined as follows. Given a graph G ∈ C and an ov-triangle T of G one has to decide whether T is representable as non-Helly triangle. The globally invariant non-Helly triangle representability problem has the additional requirement that the vertex set selector which is computed by a solving algorithm must be globally invariant.
The (globally invariant) interval triangle representability can be defined analogously asking whether an ov-triangle is representable as interval triangle.

Fact 4.11. The globally invariant non-Helly triangle representability problem is polynomial time reducible to the recognition problem for uniform CA graphs.
Proof. Given a graph G and an ov-triangle T of G determine if G is a uniform CA graph. If not then reject the input. Otherwise compute a representation ρ ∈ N (G) and accept iff T is represented as non-Helly triangle in ρ.

Definition 4.12.
Let G be a CA graph and T = {u, v, w} is an ov-triangle of G. We say v is amidst u and w if one of the following conditions holds: 1. N T (u) and N T (w) are non-empty 2. there exists a z ∈ N T (u, w) such that {u, w, z} ∈ T NHT (G) Definition 4.13. Let G be a CA graph and u ∈ V (G). Let the binary relation ∼ u on N ov (u) be defined such that x ∼ u y holds if one of the following holds: 1. x = y 2. x cd y or x cs y 3. x ov y, {u, x, y} / ∈ T NHT (G) and u is not amidst x and y Lemma 4.14. Let G be a uniform CA graph and T = {u, v, w} is an ov-triangle of G with T / ∈ T NHT (G). Then the following statements are equivalent: Proof. "2 ⇒ 1": Let ρ be in N (G) such that ρ(v) ⊂ ρ(u) ∪ ρ(w) and assume that v is not amidst u, w. Since v overlaps with u and w it holds that For z to intersect with u and w in ρ it must hold that {u, w, z} is represented as non-Helly triangle in ρ. This contradicts the assumption that v is not amidst u, w. "1 ⇒ 3": Let v be amidst u and w and assume that there exists a ρ ∈ N (G) such that ρ(v) ⊂ ρ(u) ∪ ρ(w). Since T / ∈ T NHT (G) and G is uniform it follows by Theorem 4.7 that T must be represented as interval triangle in every representation, which includes ρ. We assume w.l.o.g. that ρ(w) ⊂ ρ(u) ∪ ρ(v). From that it follows that N T (w) is empty and therefore there must be a z ∈ N T (u, w) such that {u, w, z} is a non-Helly triangle in ρ, which is impossible. "3 ⇒ 2": clear.

Lemma 4.15.
For every uniform CA graph G and u ∈ V (G) it holds that the partition induced by ∼ u equals the unique u-ov-partition P u . Stated differently, x ∼ u y iff x and y are in the same part of P u .
Proof. "⇒": Let x ∼ u y and assume for sake of contradiction that x and y are not in the same part of the u-ov-partition. This means there exists a representation ρ ∈ N (G) such that ρ(x) and ρ(y) contain different endpoints of ρ(u). This is only possible if x and y overlap. Since {u, x, y} / ∈ T NHT (G) this means {u, x, y} must be represented as interval triangle in ρ. In order for ρ(x) and ρ(y) to contain different endpoints of ρ(u) it must hold that ρ(u) ⊂ ρ(x) ∪ ρ(y), which implies that u is amidst x and y by Lemma 4.14. This contradicts x ∼ u y.
"⇐": Let x and y be in the same part of the u-ov-partition and assume that x ∼ u y does not hold. This implies that x and y must overlap and therefore {u, x, y} form an ov-triangle. For x ∼ u y to not hold it must be either the case that {u, x, y} is only representable as non-Helly triangle or u is amidst x and y. In both cases this contradicts x and y being in the same part of the u-ov-partition. Proof. The non-Helly triangle representability and interval triangle representability problem for uniform CA graphs are logspace-equivalent because they are complementary in the sense that an ov-triangle is representable as non-Helly triangle iff it is not representable as interval triangle. This follows from the fact that an ov-triangle can only be either represented as non-Helly triangle or interval triangle and these two possibilities are mutually exclusive in the case of uniform CA graphs. As a consequence these two problems are trivially reducible to the representation problem for uniform CA graphs. Given a uniform CA graph G, an ov-triangle T of G and a representation ρ ∈ N (G) it holds that T ∈ T NHT (G) iff T / ∈ T IT (G) iff T is represented as non-Helly triangle in ρ.
The representation problem is obviously reducible to the canonical representation problem. Therefore it remains to show that the canonical representation problem for uniform CA graphs is reducible to the non-Helly triangle representability problem. To obtain a canonical representation for a uniform CA graph we can use the invariant flip set function given in Lemma 4.4. To compute this function we need to figure out the unique ov-partitions for every vertex. By Lemma 4.15 this can be done by computing the equivalence relation ∼ u for each vertex u. It can be verified that this relation is computable in logspace using oracle queries of the form T ∈ T NHT (G).
Ideally, we would like to reduce the canonical representation problem for CA graphs to that for non-uniform CA graphs since we already know how to solve the uniform case. The obvious reduction for this requires recognizing uniform CA graphs. However, from Fact 3.8 in the previous section we know that it suffices to compute a globally invariant flip set function. Also, computing such a function is potentially easier than recognizing uniform CA graphs. We show that solving the globally invariant non-Helly triangle representability problem for uniform CA graphs corresponds to computing a certain globally invariant flip set function for uniform CA graphs. Proof. Let C be a subclass of uniform CA graphs. For a graph G and an ov-triangle T of G let T be in the set ∆ G iff the supplied oracle that solves the globally invariant non-Helly triangle representability problem answers yes on input G, T . We define the relation ∼ * u identical to ∼ u with the exception that we replace the set T NHT (G) in Definition 4.12 and 4.13 with the set ∆ G . It is clear that ∼ u and ∼ * u coincide if G is in C since then ∆ G = T NHT (G). Additionally, let P * u be the set of equivalence classes induced by ∼ * u and If G is in C then F * uniform (G) = F uniform (G) and therefore this is an invariant flip set function for C. It can be checked that F * uniform is computable in logspace using ∆ G as oracle. It remains to argue that F * uniform is globally invariant. Consider two isomorphic graphs G, H with disjoint vertex sets and X ⊆ V (G), Y ⊆ V (H) such that X and Y are in the same orbit and X ∈ F * uniform (G). Let X ∈ F * uniform (G) with X = {u} ∪ N cd (u) ∪ N cc (u) ∪ P and P ∈ P * u . Let π be an isomorphism from G to H with π(X) = Y and u = π(u). Then we need to show that Y ∈ F * uniform (H) which we do by proving that Y = {u } ∪ N cd (u ) ∪ N cc (u ) ∪ P with P ∈ P * u holds. It is evident that N cd (u ), N cc (u ) and u are in Y . Let Y = Y \ ({u} ∪ N cd (u ) ∪ N cc (u )). It remains to show that Y ∈ P * u . To see that this is the case we claim that ( ): x ∼ * u y holds iff x ∼ * u y holds for all x, y ∈ N ov (u) and x = π(x) and y = π(y). Since π is a bijective correspondence between X and Y and π(X \ P ) = Y \ Y it follows that π(P ) = Y . From our claim we can infer that if P ∈ P * u then π(P ) = Y ∈ P * u . To prove our claim ( ) we start by showing that the direction "⇒" holds. Let x ∼ * u y hold. Then one of the three conditions of Definition 4.13 must be satisfied. If it is one of the first two then clearly the same condition also applies to x and y , for instance x = y iff x = y . Therefore we assume that x ov y, {u, x, y} / ∈ ∆ G and u is not amidst x and y. It is apparent that x ov y iff x ov y and since ∆ G is globally invariant by definition {u, x, y} ∈ ∆ G iff {u , x , y } ∈ ∆ H . Since the exclusive neighborhoods used in Definition 4.12 are invariant under isomorphism as well it holds that u is amidst x and y iff u is amidst x and y given that T NHT (G) is replaced by ∆ G . The same argument confirms the other direction "⇐".

Corollary 4.18. The canonical representation problem for CA graphs is logspace reducible to the canonical representation problem for non-uniform CA graphs and the globally invariant non-Helly triangle representability problem for uniform CA graphs.
Alternatively, if one only aims at solving the isomorphism problem for CA graphs instead of the canonical representation problem then it already suffices to consider non-uniform CA graphs.
Theorem 4.19. The isomorphism problem for CA graphs is polynomial time reducible to the isomorphism problem for non-uniform CA graphs.
Proof. Notice, that to solve the isomorphism problem for a graph class C it suffices to find an algorithm which outputs an isomorphism whenever the two input graphs are isomorphic and in C. If the input graphs are non-isomorphic then the output of the algorithm can be arbitrary. Therefore we assume the input graphs G and H to be isomorphic CA graphs. It holds that either G and H are both uniform or non-uniform. In each case it is guaranteed that we can find an isomorphism between G and H by either applying Theorem 4.5 or the oracle. This can also be implemented as many-one reduction.

Non-Uniform CA Graphs and Restricted CA Matrices
In this section we show that every non-uniform CA graph contains a special induced 4-cycle which constrains the structure of the whole graph. As a consequence the absence of certain induced subgraphs in a CA graph imply that it must be uniform. Furthermore, we introduce the class of restricted CA matrices and show that the canonical representation problem for CA graphs reduces to the canonical representation problem for vertex-colored restricted CA matrices. This subclass of CA matrices describes in a precise sense the intersection structure that a CA graph must have with respect to some induced 4-cycle in order to be non-uniform. As an intermediate step in proving this reduction we define a subset of uniform CA graphs called ∆-uniform and show that the globally invariant non-Helly triangle representability problem for these CA graphs is decidable in logspace. It then suffices to convert CA graphs which are not ∆-uniform into restricted CA matrices.
First, let us show that if a CA graph contains an ov-triangle T which is representable as both interval triangle and non-Helly triangle then this implies the existence of another ov-triangle T such that T and T have exactly one vertex in common and the remaining four vertices form an induced 4-cycle.

Theorem 5.2. A CA graph G is non-uniform iff G has a non-uniform witness.
Proof. "⇒": Let G be a non-uniform CA graph. Due to Theorem 4.7 there exists an ov-triangle T of G with T ∈ T IT (G) ∩ T NHT (G). Let T = {u, v, w} and ρ I ∈ N (G) such that v is in-between u and w, i.e. ρ I (v) ⊂ ρ I (u) ∪ ρ I (w). First, we show that there exists an induced 4-cycle C = (u, w, w , u ) in G.
and because w is disjoint from u and w intersects with both u and w it follows that w overlaps with u and w. Therefore C = (u, w, w , u ) is an induced 4-cycle in G.
It remains to show that {u , v, w } is an ov-triangle and that it is in both T IT (G) and T NHT (G). Consider the representation ρ I from before. Assume for the sake of contradiction that v does not overlap with u . Then due to ρ I it must be the case that u is disjoint from v and thus u ∈ N T (u). However, due to fact that T is representable as non-Helly triangle this would imply that u is contained by u, which is clearly not the case. Therefore u overlaps Let us call the graph on 6 vertices and 5 edges which has a planar embedding resembling the letter 'E' the E-graph.

Fact 5.3. A CA graph is minimally non-uniform if no proper induced subgraph of it is a non-uniform CA graph. The graphs 3K 2 and E are the only two minimally non-uniform CA graphs.
Proof. It is not difficult to check that 3K 2 and E are non-uniform. See Figure 7 for CA models of these graphs. By removing a vertex in 3K 2 or E they become uniform or one vertex becomes a universal vertex. Therefore they are minimally non-uniform.
It remains to argue that every non-uniform CA graph contains 3K 2 or E and therefore these are the only two minimally non-uniform CA graphs. Let G be a non-uniform CA graph. By Theorem 5.2 it follows that there exists an non-uniform witness (C, v) with C = (u, w, w , u ). Since G does not contain a universal vertex it holds that V (G)\N [v] is nonempty. Due to the fact that {u, v, w} and {u , v, w } can be represented as interval triangle it follows that . Then the vertices u, w, u , w , v, x form an induced 3K 2 -subgraph of G. Otherwise it must hold that x ∈ (N C (u, u ) ∪ N C (w, w )) \ N [v]. Then u, w, u , w , v, x form an induced E-subgraph of G. In the second paragraph of this section we talked about the intersection structure that a non-uniform CA graph must have with respect to some induced 4-cycle. In the following we formalize this notion. Definition 5.5. Let λ be an intersection matrix, k ∈ N, x 1 , . . . , x k ∈ V (λ) and α 1 , . . . , α k ∈ {cc, cd, cs, di, ov}. For a y ∈ V (λ) \ {x 1 , . . . , x k } we say y is an (α 1 , . . . , α k )-neighbor of (x 1 , . . . , x k ) if for all 1 ≤ i ≤ k it holds that λ xi,y = α i .
For instance, given an intersection matrix λ and u = v ∈ V (λ) it holds that u is a cd-neighbor of v iff λ v,u = cd. For a CA graph this is meant to be interpreted with respect to its neighborhood matrix. cs ov cs ov di di di di ov ov ov cs ov ov di di ov w di di di di cs ov cs ov di di ov ov ov cs ov ov ov w di di di di cs cs ov ov ov ov di di ov ov ov cs ov u cs cs ov ov di di di di ov cs ov ov di di ov ov ov Table 2 Intersection types that occur in non-uniform CA graphs with non-uniform witness cycle C = (u, w, w , u ) and have no cd-entry Definition 5.6. Let α ∈ {cc, cd, cs, di, ov} 4 . We say α occurs as intersection type of non-uniform CA graphs if there exists a non-uniform CA graph G with non-uniform witness (C, v) and x ∈ V (G) \ C such that x is an α-neighbor of C.
For instance, (ov, ov, di, di) does not occur as intersection type of non-uniform CA graphs for the following reason. Assume that there exists a non-uniform CA graph G with non-uniform witness (C, v), C = (u, w, w , u ) and x ∈ V (G) such that x is a (ov, ov, di, di)- This contradicts x ∈ N C (u, w).
In Table 2 a subset of intersection types that occur in non-uniform CA graphs is listed. In fact, this table does exactly list those intersection types that occur in non-uniform CA graphs which do not have a cd-entry. The graphs X 1 and X 2 in Figure 7 show that every intersection type listed in Table 2 does occur in non-uniform CA graphs.
We define a restricted CA matrix to be a CA matrix which has an induced 4-cycle C such that every vertex not in C is an α-neighbor of C where α is a column in Table 2. We use the following more concise definition for restricted CA matrices and show that this is equivalent. Definition 5.7 (Restricted CA Matrix). Let λ be a CA matrix. We say λ is a restricted CA matrix if it contains an induced 4-cycle C = (u, w, w , u ) called witness cycle such that: 1. N C (u, w), N C (u , w ) and N C (x) are empty for every x ∈ C 2. For all x ∈ N C (C) it holds that x overlaps with all vertices in C Lemma 5.8. A CA matrix λ is restricted iff λ contains an induced 4-cycle C = (u, w, w , u ) such that for all vertices x ∈ V (λ) \ C there exists a column α in Table 2 such that x is a α-neighbor of C.
Proof. We use the numbers in the table headline to refer to the different columns. For example, 2.3 refers to the third column from left in the second part of the table: (di, cs, ov, di).
"⇒": Let λ be a restricted CA matrix with witness cycle C = (u, w, w , u ). We need to show for every x ∈ V (λ) \ C there exists a column α in Table 2 such that x is a α-neighbor of C. Due to the definition of restricted CA matrices it must hold that x is in (exactly) one of the following seven sets: x overlaps with every vertex of C by definition. This corresponds to the last column 7.1 of the table. If x ∈ N C (u, u ) then x is disjoint from w and w . It can be checked that in that case that x is an α-neighbor of C where α must be one of the four columns in part one of the table. For the same reason if x ∈ N C (w, w ) then it is an α-neighbor of C where α corresponds to one of the two columns in the second part of the table. If x is in N C (C \ {w}) then x is disjoint from w and x overlaps with both u and w . The intersection type between x and u can be one of the following: x overlaps with u or x is contained by u or x contains u. The first two cases are covered by the third part of the table. However, if x contains u then there exists no corresponding column in the table since it does not have any cd-entries. This can be resolved by using the following observation: if x is in N C (C \ {w}) and contains u then (u, w, w , x) is a witness cycle of λ as well. As a consequence we can assume without loss of generality that a witness cycle C of λ can be chosen such that there exists no x ∈ N C (C \ {w}) which contains u . The same argument applies to the remaining three cases x ∈ N C (C \ {z}) with z ∈ {u, u , w }.
Next, we want to prove that the canonical representation problem for CA graphs is logspace-reducible to the canonical representation problem for vertex-colored restricted matrices. To do so we first define the class of ∆-uniform CA graphs for which the globally invariant non-Helly triangle representability problem can be solved in logspace. Then we show that the neighborhood matrix of every CA graph which is not ∆-uniform can be easily turned into a restricted CA matrix by flipping certain vertices. Definition 5.9. For a graph G let ∆ G be a subset of ov-triangles of G. An ov-triangle T is in ∆ G if there exist three pairwise different vertices u, v, w ∈ T such that the following holds: . To see that the second condition holds we consider a vertex x ∈ N T (u) without loss of generality. Since x is not adjacent to v and w it holds that ρ(x) ⊆ C \ (ρ(v) ∪ ρ(w)) where C denotes the whole circle. Since C \ (ρ(v) ∪ ρ(w)) ⊂ ρ(u) it follows that ρ(x) ⊂ ρ(u). Due to the fact that ρ is a normalized representation this implies that x is contained by u. To see that the third condition of ∆ G holds let u , w be vertices such that (u, w, w , u ) is an induced 4-cycle of G.
It can be checked that in any representation ρ ∈ N (G) where T is represented as non-Helly triangle it must hold that Fact 5.12. Let G be a ∆-uniform CA graph and T is an ov-triangle of G. Then the following statements are equivalent: Proof. "1 ⇒ 2": Follows from the definition of ∆-uniform CA graphs. "2 ⇒ 3": Follows from the fact that every ov-triangle must be in T IT (G) ∪ T NHT (G). "3 ⇒ 1": Follows from Lemma 5.11. Corollary 5.13. ∆-uniform CA graphs are a subset of uniform CA graphs.
Corollary 5.14. The globally invariant non-Helly triangle representability problem for ∆-uniform CA graphs can be solved in logspace.
Proof. Given a CA graph G and an ov-triangle T output yes iff T ∈ ∆ G to solve the globally invariant non-Helly triangle representability problem for ∆-uniform CA graphs. Clearly, it can be checked in logspace whether T is in ∆ G . It remains to verify that ∆ G is a vertex set invariant in order to see that this algorithm is globally invariant.
Even though not every CA graph which is not ∆-uniform is non-uniform it can be shown that such graphs also contain an induced 4-cycle with certain properties that confine the structure of the whole graph. Proof. The argument is essentially the same as the one made for the "⇒"-direction in the proof of Theorem 5.2. The difference is that instead of the stronger assumption that T ∈ T NHT (G) we only require that T ∈ ∆ G .
Since G is not ∆-uniform there exists an ov-triangle T = {u, v, w} of G such that T ∈ ∆ G and there is a representation ρ ∈ N (G) such that T is represented as interval triangle in ρ. Furthermore, let us assume w.l.o.g. that . Since u and w do not form a circle cover it must hold that there exists is non-empty. If u is disjoint from v it follows that u must be contained by u from the second condition of ∆ G . This cannot be the case and therefore u ∈ N T (u, v). For u to have a neighbor which is not adjacent to u it must hold that ρ(u ) ⊆ ρ(u). Therefore u overlaps with u and v. Let w ∈ N [u ] \ N [u]. If w ∈ N T (w) then w would be contained by w due to the second condition of ∆ G . Again, this cannot be the case and therefore w ∈ N T (v, w). From the representation ρ it follows that w must overlap with u , v and w. Then Proof. Because of Lemma 5.15 the class of CA graphs without induced 4-cycle is a subset of ∆-uniform CA graphs and due to Corollary 5.14 and Theorem 4.16 a canonical representation for such graphs can be computed in logspace.
Corollary 5.17. Helly CA graphs are a strict subset of ∆-uniform CA graphs.
Proof. Assume G is a Helly CA graph which is not ∆-uniform. Then due to Lemma 5.15 there exists an induced 4-cycle C and a vertex v not in C which overlaps with every vertex in C. In any normalized representation of G it must hold that v forms a non-Helly triangle with two vertices from C. This contradicts that G is Helly. The net graph is a ∆-uniform CA graphs which is not Helly.
Theorem 5.18. The canonical representation problem for CA graphs is logspace-reducible to the canonical representation problem for vertex-colored restricted CA matrices.
Proof. For brevity let Z denote the set of all CA graphs which are not ∆-uniform. Since the globally invariant non-Helly triangle representability problem for ∆-uniform CA graphs can be solved in logspace (see Corollary 5.14) it follows from Theorem 4.17 that the canonical representation problem for CA graphs is logspace-reducible to the canonical representation problem for Z.
For a CA graph G let us say a subset of vertices X of G is a R-flip set if λ (X) G is a restricted CA matrix. To find canonical representations for Z we construct an invariant vertex set selector f such that f (G) contains at least one R-flip set for every G ∈ Z. Then to obtain a canonical representation for G ∈ Z letX denote the R-flip set in f (G) such that canon(λ (X) G , cX ) is lexicographically minimal with c X being the coloring which assigns every vertex v ∈ X the color red and the other vertices are blue. Let ρ be a canonical normalized representation for (λ (X) G , cX ). Then ρ (X) is a canonical representation for G. Notice, that ρ (X) can be computed in logspace by using an oracle to compute canonical representations for two-colored restricted CA matrices. The correctness of this approach follows from the same argument made in the proof of Theorem 3.7 in the flip trick section. The analogy is straightforward. The R-flip sets in this context correspond to flip sets and the invariant vertex set selector f takes the place of the invariant flip set function. Given a CA graph G and X ⊆ V (G) it can be easily checked in logspace whether λ (X) G is a restricted CA matrix. For a CA graph G let C(G) denote the set of all ordered induced 4-cycles in G. Now, we claim that the following logspace-computable function f is an invariant vertex set selector with the desired property: It is not difficult to check that f is invariant. It remains to argue why f (G) contains at least one Z-flip set for every G ∈ Z. Let G ∈ Z and C = (u, w, w , u ) is an induced 4-cycle The existence of such an induced 4-cycle is guaranteed by Lemma 5.15. Observe that if there exists a u 1 ∈ N C (u, w, u ) with u 1 cs u then C 1 = (u 1 , w, w , u ) also satisfies the previous condition N [u 1 ] ∪ N [w] = V (G). Therefore we can assume that there exists no z ∈ C and z 1 ∈ N C (N [z] ∩ C) such that z 1 cs z. We prove that λ (X) is a restricted CA matrix with witness cycle C where λ is the neighborhood matrix of G and X = {x ∈ V (G) \ C | ∃y ∈ C : x cs y}. Note that X ∈ f (G) via C. To reference the neighborhoods of G (which are the same as the ones of λ) or λ (X) we write N G and N λ (X) to distinguish between them. First, we show that N λ (X) C (u, w) = ∅. Assume the opposite, i.e. there exists x ∈ N λ (X) C (u, w). If x was not flipped, i.e. x / ∈ X, then it also holds that x ∈ N G C (u, w), which contradicts that N G C (u, w) is empty. If x was flipped, i.e. x ∈ X, then it must be the case that x contains u and w in λ. This , contradiction. For the same reason it holds that N λ (X) C (u , w ) and N λ (X) C (z) are empty for all z ∈ C. It remains to show that for all x ∈ N λ (X) C (C) it holds that x overlaps with all vertices of C in λ (X) . Notice that λ (X) x,z ∈ {ov, cs, cc} for every z ∈ C. Otherwise x would not be in N C (C). We consider the following two cases: in the first one we assume that x contains one vertex of C in λ (X) and in the second one we assume that x forms a circle cover with one vertex of C in λ (X) . We prove that neither of these cases can occur and therefore x must overlap with all vertices of C in λ (X) . For case one assume that w.l.o.g. x contains u in λ (X) and intersects with the other vertices of C in λ (X) . If x ∈ X then it was flipped. It follows that x was disjoint from u in λ and therefore x ∈ N G C (w, w , u ). Since x ∈ X it also must hold that x contains at least one of the vertices w, w , u in G. It follows that x contains w since it cannot contain the other two in λ. However, this contradicts our choice of C which says that there exists no w 1 ∈ N G C (w, w , u ) such that w 1 contains w in λ. If x / ∈ X then it must hold that x already contained u in λ. But then x should be in X, contradiction. For the second case assume x forms a circle cover with u in λ (X) . If x forms a circle cover with u then this implies that x contains w in λ (X) and therefore this reduces to the first case. This concludes that both conditions of Definition 5.7 are satisfied and hence λ (X) is a restricted CA matrix. Proof. We show that an invariant flip set function f for restricted CA matrices is an invariant flip set function for vertex-colored restricted CA matrices as well. Notice, that a coloring does not affect the property of being a flip set. Therefore f (λ) contains at least one flip set for every vertex-colored restricted CA matrix (λ, c). It remains to argue that f is invariant for vertex-colored restricted CA matrices. This means for every pair of isomorphic vertex-colored restricted CA matrices (λ, c) ∼ = (µ, d) it must hold that π(X) ∈ f (µ) ⇔ X ∈ f (λ) for all isomorphisms π from (λ, c) to (µ, d). Since every isomorphism from (λ, c) to (µ, d) is also an isomorphism from λ to µ this property follows from the fact that f is invariant in the uncolored case. Now, we can apply Theorem 3.7 with a slight modification in the proof to account for the coloring. Given a colored restricted CA matrix (λ, c) we associate a flip set ). By adding the originial coloring c to c the colored interval matrix I X λ preserves the isomorphism type of (λ, c). More precisely, for two vertex-colored restricted CA matrices (λ, c) and (µ, d) it holds that π is an isomorphism from (λ, c) to (µ, d) whenever π is an isomorphism from I X λ to I Y µ .

Flip Sets for Restricted CA Matrices
In section two we briefly considered computing invariant u-flip sets for CA graphs in general. This seemed to be a hopeless task given the lack of structure that one could use and hence we defined uniform CA graphs. However, now due to Theorem 5.18 and 5.19 from the previous section we know that it suffices to compute invariant flip sets for restricted CA matrices in order to solve the canonical representation problem for CA graphs. As we have seen a restricted CA matrix λ with witness cycle C offers considerably more structure that can be used to find flip sets than an arbitrary CA graph. We show that finding invariant flip sets for restricted CA matrices boils down to understanding how a certain subset of vertices can be represented. Since more 'initial structure' can be assumed in a restricted CA matrix using a witness cycle we consider the following refined version of u-flip sets. Definition 6.1. Given a CA matrix λ and two vertices u, w of λ with u ov w. We say the w-endpoint of u in a representation ρ ∈ N (λ) is the endpoint of ρ(u) which is contained in ρ(w). A flip set X of λ is a (u, w)-flip set if there exists a representation ρ ∈ N (λ) such that x ∈ X iff ρ(x) contains the w-endpoint of u in ρ for all x ∈ V (λ).
As it is clear from the context we will say that x (instead of ρ(x)) contains the w-endpoint of u in ρ. Notice that (u, w)-flip sets can be equivalently defined as u-flip sets which contain w. Now, our goal is given a restricted CA matrix λ with witness cycle C = (u, w, w , u ) to compute invariant (u, w)-flip sets (to be exact, we will compute (u 1 , w)-flip sets where u 1 is a vertex similar to u). As we shall see for many vertices of λ it is clear whether they belong to a (u, w)-flip set or not. The only set of vertices that poses an obstacle is N C (C). Therefore we are actually interested in computing the following kind of subsets of N C (C). Definition 6.2 (C-partial flip set). Let λ be a restricted CA matrix with witness cycle C = (u, w, w , u ). We call a subset Z of N C (C) a C-partial flip set if there exists a subset Y of V (λ) \ N C (C) such that Y ∪ Z is a (u, w)-flip set.
Recall that a vertex x ∈ N C (C) overlaps with every vertex from C. In a normalized representation of λ there are four choices how x can be placed with respect to C. The following definition and Figure 8 describe these four choices. Definition 6.3 (Type). Let λ be a restricted CA matrix with witness cycle C = (u, w, w , u ). Given x ∈ N C (C) and y, z ∈ C we define type λ,C (x, ρ) as {y, z} such that ρ(x) ⊂ ρ(y) ∪ ρ(z).
If λ and C are clear from the context we omit the subscript. Lemma 6.4. Given a restricted CA matrix λ with witness cycle C = (u, w, w , u ). Let Z be a subset of N C (C). Then the following statements are equivalent: 1. Z is a C-partial flip set 2. There exists a representation ρ ∈ N (λ) such that z ∈ Z iff ρ(z) contains the w-endpoint of u in ρ for all z ∈ N C (C) 3. There exists a representation ρ ∈ N (λ) such that z ∈ Z iff w ∈ type(z, ρ) for all z ∈ N C (C) Proof. Observe that for every x ∈ N C (C) and ρ ∈ N (λ) it holds that x contains the wendpoint of u iff w ∈ type(x, ρ). From this it follows that the second and third statement are equivalent. It is also easy to see that the first implies the second statement. Let Z be a C-partial flip set. This means there exists a Y ⊆ V (λ) \ N C (C) such that Y ∪ Z is a (u, w)-flip set. The second statement follows from that. To see that the second statement implies the first consider a representation ρ ∈ N (λ) such that z ∈ Z iff ρ(z) contains the w-endpoint of u in ρ for all z ∈ N C (C). Let Y contain all vertices x ∈ V (λ) \ N C (C) such that ρ(x) contains the w-endpoint of u in ρ. Clearly, Y ∪ Z is a (u, w)-flip set and therefore Z is a C-partial flip set. Definition 6.5. Let f be a vertex set selector for restricted CA matrices. We call f a partial flip set function for restricted CA matrices if for every restricted CA matrix λ there exists a witness cycle C of λ such that f (λ) contains a C-partial flip set. We call f an invariant partial flip set function if it is invariant for restricted CA matrices. Proof. Due to Theorem 5.18 and 5.19 it suffices to compute an invariant flip set function for restricted CA matrices in logspace. Let f be an invariant partial flip set function for restricted CA matrices. Then we claim that the following vertex set selector is an invariant flip set function for restricted CA matrices. Let C 4 (λ) denote the set of all ordered induced 4-cycles of λ.
Clearly, if f can be computed in logspace then this also holds for F . The fact that F is invariant follows from f and the different neighborhoods used in F being invariant and the set of induced 4-cycles C 4 (λ) being a vertex set invariant as well.
It remains to prove that F (λ) contains at least one flip set for every restricted CA matrix λ. Let Z ∈ f (λ) be a C-partial flip set of λ with witness cycle C = (u, w, w , u ). Additionally, let ρ ∈ N (λ) be a representation such that x ∈ Z iff w ∈ type(x, ρ) for all x ∈ N C (C). The existence of such a representation follows from Lemma 6.4. Let u 1 ∈ U denote the vertex such that ρ(u 2 ) ∩ ρ(w) ⊆ ρ(u 1 ) ∩ ρ(w) for all u 2 ∈ U . Informally, u 1 is the 'rightmost' vertex of u in ρ. We show that the set with X ∈ F (λ) is a (u 1 , w)-flip set of λ. This follows from the following two claims: 1. For all x ∈ N C (C) it holds that ρ(x) contains the w-endpoint of u 1 iff w ∈ type(x, ρ) 2. For all x ∈ V (λ) \ N C (C) with x = u 1 it holds that ρ(x) contains the w-endpoint of u 1 iff x ∈ (N [u 1 ] ∩ N [w]) \ U ) For the first claim consider a vertex x ∈ N C (C). Note that the w-endpoint of u 1 in ρ is contained in A = ρ(w) \ (ρ(u) ∪ ρ(w )). If w ∈ type(x, ρ) then A ⊆ ρ(x) and therefore ρ(x) contains the w-endpoint of u 1 in ρ. If w / ∈ type(x, ρ) then ρ(x) ∩ A = ∅ and therefore ρ(x) does not contain the w-endpoint of u 1 in ρ.
For the second claim let us first define the following sets similar to U : w ) It holds that these sets together with U and N C (C) partition V (λ). Then the set (N [u 1 ] ∩ N [w]) \ U in the second claim is identical to (W ∪ W ∪ W W ) ∩ N [u 1 ] when restricted to vertices from V (λ) \ N C (C). Note that the other endpoint of u 1 (not the w-endpoint) is contained in ρ(u) ∩ ρ(u ). If x ∈ W ∪ W ∪ W W and adjacent to u 1 then it must overlap with u 1 . Since ρ(x) ∩ (ρ(u) ∩ ρ(u )) = ∅ it holds that ρ(x) cannot contain the other endpoint of u 1 in ρ. Therefore ρ(x) contains the w-endpoint of u 1 . If x / ∈ W ∪ W ∪ W W then x ∈ U ∪ U ∪ U U . If x ∈ U ∪ U U then x is disjoint from w and therefore ρ(x) does not contain the w-endpoint of u 1 . If x ∈ U and x = u 1 then ρ(x) ∩ ρ(w) ⊂ ρ(u 1 ) ∩ ρ(w) since we have chosen u 1 to satisfy this. Therefore x does not contain the w-endpoint of u 1 in this case as well.

Conclusions and Future Research
We set out with the goal to compute canonical representations for CA graphs. By formalizing the idea of using flip sets to find canonical representations for CA matrices we were able to show that in the case of uniform CA graphs the canonical representation problem is logspaceequivalent to the non-Helly triangle representability problem. Moreover, we showed that the canonical representation problem for CA graphs reduces to the quite specific problem of computing an invariant partial flip set function for restricted CA matrices. It seems plausible that further investigation of C-partial flip sets might lead to a polynomial time (or even logspace) algorithm for the canonical representation problem for CA graphs. Also, if a C-partial flip set for a restricted CA matrix can be computed in logspace then CA graphs can be recognized in logspace and therefore this problem is logspace-complete. Another task we deem worth pursuing is solving the globally invariant non-Helly triangle representability problem for uniform CA graphs or the potentially more difficult problem of recognizing uniform CA graphs. Solving this problem would mean that it suffices to consider only non-uniform CA graphs when trying to find canonical representations for CA graphs. In terms of restricted CA matrices this would mean that one only needs to look at restricted CA matrices that have a non-uniform witness (C, v), i.e. an induced 4-cycle C = (u, w, w , u ) and a vertex v such that {u, v, w} and {u , v, w } are representable as both interval and non-Helly triangle. The structure of restricted CA matrices which have such non-uniform witnesses is subject to even more constraints, which might be useful when trying to compute C-partial flip sets. A possible approach to solve the globally invariant non-Helly triangle representability problem would be to extend Definition 5.9 of the set ∆ G until ∆ G = T NHT (G) for every uniform CA graph G.
A more open-ended question is whether the abstract idea of finding invariant flip sets can be applied to solve isomorphism for other graph classes. More concretely, are there examples of natural graph classes C and D and a reversible operation f which given a graph G and a set of vertices X of G returns a new graph f (G, X) such that for every graph G ∈ C there exists a 'flip set' X ⊆ V (G) which turns G into a graph of D by applying f , i.e. f (G, X) ∈ D. This would mean that the isomorphism problem for C can be reduced to the isomorphism problem for vertex-colored D if invariant flip sets can be computed effectively.