# Graphs of unbounded linear cliquewidth must transduce all trees

Mikolaj Bojanczyk, Pierre Ohlmann

► To cite this version:

Mikolaj Bojanczyk, Pierre Ohlmann. Graphs of unbounded linear cliquewidth must transduce all trees. 2025 40th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), Jun 2025, Singapore, Singapore. pp.691-703, 10.1109/LICS65433.2025.00058. [https://hal.science/hal-05376866](https://hal.science/hal-05376866) [https://doi.org/10.1109/LICS65433.2025.00058](https://doi.org/10.1109/LICS65433.2025.00058). [hal-05376866](https://hal.science/hal-05376866)

HAL Id: hal-05376866

https://hal.science/hal-05376866v1

Submitted on 21 Nov 2025

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Graphs of unbounded linear clique-width must transduce all trees

Mikołaj Bojańczyk and Pierre Ohlmann

**Abstract**—The Pathwidth Theorem states that if a class of graphs has unbounded pathwidth, then it contains all trees as graph minors. We prove a similar result for dense graphs: if a class of graphs has unbounded linear clique-width, then it can produce all trees via some fixed msO transduction.

## I. INTRODUCTION

We begin by stating the main result of the paper (the appropriate notions will be explained later in the introduction and the preliminaries).

**Theorem 1.1.** If a class *C* of graphs has bounded clique-width, then either:

1) *C* has bounded linear clique-width; or

2) there is a surjective msO transduction from *C* to trees.

Our results can be seen as a dense analogue of the Pathwidth Theorem of Robertson and Seymour [23], which states that a class of graphs has either bounded pathwidth, or it has all trees as graph minors. In our paper, the role of graph minors for dense graphs is played by msO transductions. (This point of view is mainly useful for tree-like graphs.) From this point of view, our paper can be seen as a step in the project of generalising graph minor theory to dense graphs. An alternative point of view is to use vertex minors [19], and we comment on this point of view in the conclusion section.

**Context and prior work:** Broadly speaking, this paper is about the interplay between structural graph theory and logic, mainly monadic second-order logic msO. The foundational result is Courcelle's Theorem [10], which shows that for graphs of bounded treewidth, properties expressible in msO can be recognised by automata. The result is particularly known for its algorithmic consequence, which is that msO model checking can be done in linear time for graphs of bounded treewidth, since tree decompositions can be computed in linear time [3].

To place our result in context, we relate it to prior work on the transduction ordering for graph classes, and show how we extend that work from sparse graphs to dense graphs. Before further describing this prior work, we need to clarify the notion of msO, since there are several non-equivalent variants under consideration. The first choice of variant concerns the way in which graphs are represented as logical structures:

1) In the incidence representation, the universe (i.e. the domain of quantification) is the vertices and edges, and there is a binary relation for incidence. This representation is used when studying sparse graphs and treewidth.

2) In the adjacency representation, the universe is the vertices, and there is a binary relation for the edges. This representation is used when studying dense graphs and clique-width.

The second choice concerns modulo counting:

1) We write msO for the logic without modulo counting.

2) We write cMSO for the extension with modulo counting. It is equipped with predicates of the form “the size of set X is divisible by m”, for every m ∈ {2, 3, 4, ...}.

Together, we have four possible combinations, with the least expressive one being msO under the adjacency representation, and the most expressive one being cMSO under the incidence representation.

**Transductions:** In the study of msO on graphs, a prominent role is played by msO transductions [1], [11], [15]. These are graph-to-graph transformations, which define the output graph using msO formulas that are evaluated in the input graph. The transformations are nondeterministic, which means that one input graph can produce several output graphs. The nondeterminism arises from a colouring of the input graph that is chosen nondeterministically. Following Blumensath and Courcelle [2], we are interested in the transduction order on classes of graphs, where $C \leq D$ holds if there is some msO transduction from $D$ to $C$ which is surjective, i.e. every graph from $C$ is obtained as an output<fnref n="1" /> from some graph in $D$. This order comes in four flavours, depending on whether we use msO or cMSO, and whether we use the adjacency or incidence representation. We indicate these flavours by annotating the order relation, e.g. $\leq_{adj}^{MSO}$ refers to the transduction order that uses msO and the adjacency representation. All the technical work in this paper relates to the variant $\leq_{adj}^{MSO}$, but we discuss the other ones in this introduction to place our work in context.

**Sparse graphs and the incidence representation:** We begin by explaining the prior work on the transduction ordering under the incidence representation. This representation corresponds to treewidth (and thus sparse graphs), as justified by the following result of Courcelle and Engelfriet [12]:

$$C \text{ has bounded treewidth} \iff C \leq_{\text{inc}}^{\text{MSO}} \text{Trees.} \quad (1)$$

The above equivalence would remain valid if msO was replaced with cMSO. In fact, all results about the transduction order under incidence representation that we discuss here

<footnote n="1">¹ The transduction can output graphs that are not in *C*. All we care about is that it outputs all graphs in *C*. This distinction is relevant when *C* is not definable in msO.</footnote>
are true for both MSO and CMSO [2, p. 26], so we no longer indicate the logic in the following discussion. Unbounded treewidth can also be described in terms of transductions, namely classes of unbounded treewidth are exactly those that can transduce all graphs (and are thus maximal, since nothing more can be transduced):

$$C \text{ has unbounded treewidth} \Leftrightarrow \text{Graphs } \leq_{\text{inc}} C. \quad (2)$$

This is a consequence of the Grid Minor Theorem of Robertson and Seymour [24], since graph minors are a special case of MSO transductions, and general graphs can be transduced from grids. (These observations are due to Seese [25].) Putting together (1) and (2), we get a dichotomy: there is nothing between trees and graphs in the transduction order under the incidence representation.

Let us now examine classes that are strictly below the class of all trees, for example the class of all paths. Blumensath and Courcelle [2] gave a complete classification of such classes:

**Theorem 1.2.** Let $\leq$ be the transduction ordering, using MSO and the incidence representation. Then every class of graphs is equivalent to exactly one of the following classes:

$$\underbrace{\text{Trees}_0 < \text{Trees}_1 < \text{Trees}_2 < \dots < \text{Paths} < \text{Trees} < \text{Graphs}}_{\text{trees of height at most } k = 0, 1, 2, \dots}$$

The order does not change if we use MSO instead of CMSO.

They also asked if the same situation holds under the adjacency representation [2, Open Problem 9.3]. In this paper, we give a positive answer to this question, see Theorem I.3.

**Adjacency representation:** Let us now discuss the transduction order under the adjacency representation. This corresponds to cliquewidth and dense graphs, thanks to the following analogue of (1), which was also proved by Courcelle and Engelfriet [12]:

$$C \text{ has bounded cliquewidth} \Leftrightarrow C \leq_{\text{adj}}^{\text{MSO}} \text{Trees}. \quad (3)$$

As in the case of treewidth, the above equivalence would remain valid if we replaced MSO with CMSO. An analogue of (2) also holds for dense graphs, if we allow counting:

$$C \text{ has unbounded cliquewidth} \Leftrightarrow \text{Graphs } \leq_{\text{adj}}^{\text{CMSO}} C. \quad (4)$$

The above equivalence was proved by Courcelle and Oum [14]. The equivalence uses modulo counting, since it is based on a result of Geelen, Gerards and Whittle [17], which extends the Grid Minor Theorem from graphs to matroids over the some finite field, which necessitates counting in the field. Whether or not the equivalence (4) can be strengthened to use MSO instead of CMSO is essentially the same as the Seese Conjecture, and we do not address this question here. Therefore, up to using CMSO instead of MSO, the equiva- lences (3) and (4) tell us that there is nothing between trees and general graphs.

The next question is about what happens below trees. Here is where our results come in. (In the discussion below, all results use MSO and not CMSO, which makes them stronger.)

A consequence of our main result, Theorem I.1, is that there is nothing between trees and paths. This is because classes that are transduced from paths are exactly those of bounded linear cliquewidth. Unlike the dichotomies discussed before, we cannot call upon an existing result in structural graph theory, since there is no known dense analogue of the Pathwidth Theorem. Therefore, the main technical contribution of this paper is proving such a result.

Let us see now what happens below paths. As shown by Bojańczyk, Grohe and Pilipczuk [6], if a class of graphs has bounded linear cliquewidth, then there is an MSO transduction that produces the appropriate tree decompositions. This implies that every class of bounded linear cliquewidth is equivalent, in the transduction order under the adjacency representation, to some subclass of trees. If we restrict to trees, the transduction ordering does not depend on whether we use adjacency/incidence or MSO/CMSO. Therefore, we can use the results of Blumensath and Courcelle for classes that are smaller or equal to the class of paths. Summing up, from our main result in Theorem I.1, we conclude that the transduction ordering is the same<fnref n="2" /> in the adjacency case as it was in the incidence case:

**Theorem 1.3.** Let $\leq$ be the transduction ordering, using CMSO and the adjacency representation. Then every class of graphs is equivalent to exactly one of the following classes:

$$\text{Trees}_0 < \text{Trees}_1 < \text{Trees}_2 < \dots < \text{Paths} < \text{Trees} < \text{Graphs}.$$

Furthermore, for classes up to and including trees, the order does not change if we use MSO instead of CMSO.

**Outline of the paper:** After the preliminary definitions in Section II, we state in Section III the main lemma of the paper, which is called the Dichotomy Lemma. This is essentially the main theorem, but suitably modified so that it can be proved by induction. Next, in Section IV, we show that the Dichotomy Lemma can be reduced to a special case of tree decompositions, which we call uniform. The general idea is that all nodes behave similarly to each other, which is guaranteed by applying a tree version of the Factorisation Forest Theorem [27], [9]. Finally, in Section V, we prove the Dichotomy Lemma by for uniform classes. The proof shares some similarity to the proof that graphs of bounded treewidth have definable tree decompositions [8]. The main new phenomenon that arises in the present paper, as compared to [8], is the presence of half-graphs, and most of the original material consists of the analysis of such half-graphs. Due to the space constraints, almost all proofs are in an appendix.

## II. PRELIMINARIES

In this section, we give formal definitions of the standard notions used in this paper, namely transductions, logic, cliquewidth, trees and tree decompositions.

<footnote n="2">²By “same” we mean that the classes mentioned in the statement continue to represent all other classes. However, the placement of the other classes might change: as we discussed cliques are high in incidence ordering, but low in the adjacency ordering.</footnote>
We work with undirected graphs, i.e. the edge relation is symmetric and irreflexive. When talking about a class of graphs, we assume that the class is closed under graph isomorphism. Graphs are finite, although we believe that our results should extend without difficulty to infinite graphs.

### A. Logic and transductions

To express properties of graphs, we use monadic second-order logic MSO. This is the extension of first-order logic which allows quantifying over sets of elements. For a detailed description of the syntax and semantics of MSO, see [20]. In the rest of this paper, when describing properties of graphs, we use the adjacency representation, where the universe is the vertices, and there is a binary relation for the edges. We do not use the incidence representation, or the counting variant CMSO; these were only mentioned in the introduction to provide context.

We now give a formal definition of MSO transductions, which are our mechanism for transforming graphs.

**Definition II.1 (MSO transduction).** The syntax of a graph-to-graph MSO transduction is given by a number $k \in \{0, 1, \dots\}$, which is called the number of parameters, and two formulas

$$ \underbrace{\varphi_V(x, Z_1, \dots, Z_k)}_{\text{vertex formula}} \quad \text{and} \quad \underbrace{\varphi_E(x, y, Z_1, \dots, Z_k)}_{\text{edge formula}} $$

over the vocabulary of graphs (i.e. one binary relation).

The semantics of an MSO transduction is a binary relation that associates to each input graph a set of output graphs. The output graphs are defined as follows. Fix some choice of parameters $Z_1, \dots, Z_k$, which are subsets of vertices in the input graph. For each such choice, the vertex formula defines a unary relation on vertices of the input graph, and the edge formula defines a binary relation on this subset (by restricting it to the former unary relation). If the binary relation is symmetric and irreflexive, then this gives a possible output graph. The outputs of the transduction are all output graphs that arise this way, for some choice of parameters.

**Definition II.2 (Transduction order).** A class of graphs $\mathcal{C}$ transduces a class of graphs $\mathcal{D}$ if there is an MSO transduction such that every graph from $\mathcal{D}$ can be obtained as one of the possible outputs of the transduction for some graph in $\mathcal{C}$.

As mentioned in Footnote 1, the transduction may produce graphs that are not in $\mathcal{D}$. Since MSO transductions are closed under composition [13, Theorem 7.14], it follows that the relation in Definition II.2 is a preorder, which we call the transduction preorder. We are mainly interested in the relation with trees: we say that a class of graphs transduces all trees if it transduces the class of all acyclic graphs.

**Example 1.** The class of cliques is equivalent, under our transduction preorder, to the class of independent sets (i.e. graphs without edges). The corresponding transduction does not need parameters, it simply complements the edge

relation. A transduction from independent sets to cliques would be impossible under the incidence representation. □

### B. Cliquewidth

In this section, we define cliquewidth. We do this using Courcelle's algebraic, approach via a multisorted algebra that we call the cliquewidth algebra. This algebra operates on coloured graphs. Here, for $k \in \{1, 2, \dots\}$, a k-coloured graph is defined to be a graph together with a surjective function that assigns colours from $\{1, \dots, k\}$ to its vertices. From now on, all graphs will be coloured, so we will often refer to them simply as graphs. The usual graphs can be seen as the special case for $k = 1$. Here is a picture of a 2-coloured graph:

<figure><img src="image_2.png" /></figure>

We draw the colours using coloured rectangles, instead of simply assigning colours to the vertices. This is to help visualize the operations in the cliquewidth algebra.

**Elements of the algebra:** The cliquewidth algebra has one sort for each $k \in \{1, 2, \dots\}$; this sort contains all k-colored graphs. Since the algebra is multisorted, to describe the type of an operation, we need to give not only the number of arguments, but also the sorts (i.e. numbers of colours) of all input arguments and of the output. We use the following convention for writing types:

$$ \underbrace{k_1 \times \dots \times k_n}_{\text{input sorts}} \rightarrow \underbrace{k}_{\text{output sort}} $$

In the special case of zero arguments (i.e. the operation is a constant), the type is a single number $k$, and in the special case of one argument (i.e. a unary operation), the type is of the form $\ell \rightarrow k$. The basic operations of the algebra are:

* **Constant.** There is one constant, of type $k = 1$, which represents a graph that has one vertex with the unique possible colour.

* **Recolouring.** There is an infinite family of unary operations, which recolour the input graph using some prescribed surjective function. More formally, for every $\ell, k \in \{1, 2, \dots\}$ and every surjective function

$$ f : \{1, \dots, \ell\} \rightarrow \{1, \dots, k\}, $$

there is a unary basic operation of type $\ell \rightarrow k$, which applies $f$ to the colouring in the input graph.

* **Sum.** To combine graphs, we use the sum operations. For every $k_1, k_2 \in \{1, 2, \dots\}$ and every binary relation

$$ R \subseteq \{1, \dots, k_1\} \times \{1, \dots, k_2\}, $$

there is a corresponding sum operation of type

$$ k_1 \times k_2 \rightarrow k_1 + k_2. $$
The operation takes the disjoint union of the two input coloured graphs, using disjoint colours, so that the result has $k_1 + k_2$ colours. Next, for every pair $(a_1, a_2) \in R$, we add an edge from every $a_1$-coloured vertex in the first graph to every $a_2$-coloured vertex in the second graph.

This completes the definition of the clique-width algebra. The operations of the algebra can be composed, resulting in term operations. An example is what we call a sum-and-recolour operation, which is any composition of the form

$$k_1 \times k_2 \xrightarrow{\text{a sum operation}} k_1 + k_2 \xrightarrow{\text{a recolouring}} \ell.$$

We will be frequently using pictures of term operations. Here is a picture of a sum-and-recolour operation in type $5 \times 3 \to 2$:

<figure><img src="image_3.png" /></figure>

Let us explain the picture. The horizontal coloured rectangles represent the two output colours. The two vertical rounded rectangles represent the arguments, with the dots representing the input colours. The placement of the dots in the coloured rectangles represents how an input colour is mapped to an output colour. Finally, the edges represent the relation $R$.

The advantage of the sum-and-recolour operations is that they have a better colour economy, by hiding the intermediate colours $k_1 + k_2$. This is slightly non-standard; our present definition of clique-width may differ with the usual one by a factor of at most two. (This distinction is irrelevant for us as we will only care about boundedness.)

**Definition II.3 (Clique-width).** A graph has clique-width $k$ if it can be generated from the constants with sum-and-recolour operations using only sorts $\{1, \dots, k\}$.

**Example 2.** [Cliques] The paradigmatic example is the class of cliques, which has clique-width $k = 1$. To combine two cliques, we use the following sum-and-recolour operation:

<figure><img src="image_4.png" /></figure>

<figure><img src="image_5.png" /></figure>

**Linear clique-width:** When creating a graph using the clique-width algebra, we use a tree of operations, where inner nodes use sum-and-recolour, and the leaves are constants. A special case of interest is when the operations are aligned along a single branch of the tree; this case will correspond to linear clique-width, and is described below.

**Definition II.4 (Linear clique-width).** A basic linear operation is any operation that arises by taking some sum-and-recolour

operation, and substituting the constant for the first argument. The linear clique-width of a graph is defined to be the smallest number $k$ such that the graph can be generated using only sorts $\{1, \dots, k\}$, and basic linear operations.

**Example 3.** [Half-graph] A prominent role in our proof will be played by half-graphs [21, Section 1.1], as in this picture:

<figure><img src="image_6.png" /></figure>

In a half-graph, there are two rows and $n$ columns, and the edges are exactly those that go from north-west to south-east. A half-graph simulates a directed graph where the edges form a total order, using a graph where edges are undirected. One can easily see that half-graphs have linear clique-width 2. □

**Term operations as graphs:** As we have hinted in the pictures so far, a term operation in the clique-width algebra can be represented as a graph, with some extra structure (the vertical rectangles, which correspond to arguments). Here is another example, which has vertices that are not part of any argument, and which represents a term operation of type $2 \times 3 \to 3$:

<figure><img src="image_7.png" /></figure>

In this paper, we will often identify term operations with their graph representations. In the graph representation of a term operation of type $k_1 \times \dots \times k_n \to k$, we have a $k$-coloured graph, together with a non-repeating list of $k_1 + \dots + k_n$ distinguished vertices, representing $n$ different groups of vertices (the vertical rectangles). The vertices inside each group are called *ports* of the corresponding argument (the dots inside the vertical rectangles). The $i$-th argument will have $k_i$ *ports*. Within each argument, there are no edges connecting the *ports*. This is because once an argument is passed to a clique-width operation, one can no longer modify the edges inside the argument, one can only create edges to other arguments and *verticees*. We use the name *graph term of type* $k_1 \times \dots \times k_n \to k$ for the graph representation of any term operation of this type. There is a one-to-one correspondence between graph terms and term operations.

### C. Logic and compositionality

We will be interested in MSO definable properties of graph terms. Therefore, we need to be able to represent a graph term as a logical structure. We start with the adjacency
representation that was described in Section II-A, and we extend it with $k$ unary relations to represent the colours, and $k_1 + \cdots + k_n$ constants to represent the ports of all arguments. The vocabulary of this structure depends on the type of the graph term. This way, we can use MSO logic to describe properties of graph terms, in some fixed type.

We now state the classical compositionality principle of MSO. The *quantifier depth* of an MSO formula is the maximal number of quantifiers that can be found along a branch in the syntax tree of the formula. For a quantifier depth $q \in \{0, 1, \dots\}$, define the *q-theory* of a graph, or a graph term, to be the set of sentences of MSO that have quantifier depth at most $q$ and are true in the corresponding structure.

**Lemma II.5 (Compositionality).** Let $q \in \{0, 1, \dots\}$ be a quantifier depth. For every graph term and every list of graphs for its arguments, the *q-theory* of the output depends only on the *q-theories* of the term and its arguments.

We are particularly interested in unary graph terms that have a loop type, i.e. a type of the form $k \to k$. Once $k$ is fixed, such graph terms form a semigroup. By the above lemma, the function that maps such a term to its theory is a semigroup homomorphism, i.e. we have

$$ (q\text{-theory of } E) \circ (q\text{-theory of } F) = (q\text{-theory of } E \circ F), \quad (5) $$

for all unary graph terms $E$ and $F$ of type $k \to k$. In the above, the semigroup operation on the right is composition of unary graph terms, and the semigroup operation on the left is the semigroup operation on *q*-theories that arises from compositionality.

### D. Trees

Although the main result of this paper talks about transducing graphs which are trees (i.e. acyclic graphs), in the technical development of this paper we view trees as hierarchical families of subsets, as explained in the following definition.

**Definition II.6 (Tree).** A tree over a set is a family of subsets of this set, such that every two sets in the family are either disjoint, or one is contained in the other. One of the sets in the family must be the full set, which is called the root of the tree.

The sets in a tree are called its *nodes*. Here is a picture:

<figure><img src="image_8.png" /></figure>

The trees in Definition II.6 do not have a sibling order, i.e. we do not distinguish a first or a second child, and so on. We use the usual tree terminology, such as *leaves*, *child*, *parent*, *descendant*, *ancestor*. Ancestors and descendants are proper,

i.e. an ancestor is a proper superset, and a descendant is a proper subset. A *chain* is defined to be a family of nodes that are totally ordered by inclusion. If the tree $T$ is not clear from the context, then we talk about $T$-children, $T$-chains, etc.

As defined above, trees are not graphs, but families of sets. To avoid confusion, we will use the name *acyclic graph* for the graph version of trees. Of course, to each tree (in the sense used by this paper, i.e. a hierarchical family of subsets), we can associate an acyclic graph, which we call its *child graph*, where the edge relation represents the child relation. For example the tree in Picture (1) has this child graph:

<figure><img src="image_9.png" /></figure>

In our main theorem, the transductions in the second item output acyclic graphs, which are the same as child graphs of trees.

We will frequently be extracting smaller trees from larger trees, using the following notion.

**Definition II.7 (Tree minor).** A tree minor of a tree $T$ is any tree that is obtained by choosing some new root $X \in T$, restricting the underlying set to $X$, and keeping only some nodes from the original tree (necessarily contained in $X$).

The root and the underlying set could change when taking a tree minor. The notion of tree minor is compatible with the notion of graph minor used by Robertson and Seymour. More precisely, if $S$ is a tree minor of $T$, then the child graph of $S$ is a graph minor of the child graph of $T$.

**Strahler number:** We will be mainly interested in trees that branch a lot, as formalized below. A *binary tree* is a tree where every non-leaf node has exactly two children. Such a tree is called *complete* if all leaves are at the same depth. The *Strahler number* of a tree is the maximal depth of complete binary trees that are its tree minors.

### E. Tree decompositions

One perspective on tree decompositions is that they are terms constructed using the operations of the cliquewidth algebra. In this paper, we use a slightly different perspective. We think of a tree decomposition as being a graph equipped with a family of subsets, which forms a tree, together with some extra colouring information that allows us to view the nodes as coloured graphs. This point of view will be amenable to various extraction processes that we perform.

**Contextual equivalence:** In a tree decomposition, a node $X$ will describe an induced subgraph. We will want a small amount of information to flow between the subgraph and its complement, as expressed in the following definition.

**Definition II.8 (Contextual equivalence and rank).** For a graph and a subset of vertices $X$, define the contextual
equivalence relation of X to be the equivalence relation on X which identifies two vertices if they have the same colour and the same neighbours in the complement of X. Equivalence classes for this relation are called contextual classes of X.

Define the *rank* of a set X of vertices to be the number of contextual classes<fnref n="3" />. We now present our notion of tree decompositions. (These are tree decompositions corresponding to cliquewidth and not treewidth, but since this is the only kind of tree decomposition used in this paper, we simply call them tree decompositions.)

**Definition II.9 (Tree decomposition).** A tree decomposition consists of:

1) a graph;

2) a tree on its vertices;

3) for each node of the tree, an order on its contextual classes.

We now introduce some terminology for tree decompositions, and explain the purpose of the orders in item 3. The graph in item 1 is called the *underlying graph* of the tree decomposition. A node of the tree in item 2 is called a *node* of the tree decomposition. Therefore, a tree decomposition has both vertices (of the underlying graph) and nodes (which are sets of vertices). For each vertex, define the *introducing node* to be the smallest inclusion-wise (i.e. deepest in the tree) node that contains this vertex. The *width* of a tree decomposition is the maximal number of contextual classes in a node. The order in the third item is a linear order, which allows us to number the contextual classes as {1, ..., k}, where k is the rank of the node, thus equipping the subgraph induced by the node with the structure of a *k*-coloured graph.

The following straightforward lemma is an immediate consequence of the definitions.

**Lemma II.10.** A graph has cliquewidth at most *k* if and only if it admits a tree decomposition of width *k*, where:

1) every leaf is a singleton;

2) every non-leaf has two children;

3) every vertex is introduced in a leaf.

A similar result holds for linear cliquewidth. In this case, the tree decompositions are linear, which means that all nodes are on a single branch, and furthermore every node introduces at most one vertex.

In the proof of the main theorem, we will start with a tree decomposition as in Lemma II.10. Then, we will subject it to various extraction processes, during which the properties from the lemma will be lost. Nodes will have an unbounded number of children, and they will introduce an unbounded number of vertices. When extracting parts of a tree decompositions, we will be using the following notion.

**Definition II.11 (Sub-decomposition).** A sub-decomposition of a tree decomposition is obtained as follows. Take some tree minor of the tree. In the graph, keep only the vertices from the root node of the minor, and in the tree, keep only the nodes from the minor.

An example of a sub-decomposition is obtained by taking a minor which consists of a node and its children. Such a sub-decomposition is called a *local sub-decomposition*. In a local sub-decomposition, the tree has height one.

### III. THE DICHOTOMY LEMMA

In this section, we state the main technical result of this paper, which we call the Dichotomy Lemma.

The Dichotomy Lemma speaks about a class of tree decompositions; such classes will always be assumed to have bounded width. By abuse of notation, we say that a class of tree decompositions transduces all trees if the underlying graphs transduce all trees (i.e. acyclic graphs). In particular, the corresponding transductions are not allowed to refer to the nodes of the tree decomposition.

The Dichotomy Lemma says that for every class of tree decompositions of bounded width, either (a) it transduces all trees, or otherwise (b) the tree decompositions follow a strict sequential discipline, and the tree structure can be abandoned in favour of a linear order. The second alternative is meant to correspond to linear cliquewidth. When applied to tree decompositions as in Lemma II.10, the second alternative will directly imply linear cliquewidth, but we will also apply the lemma to other kinds of tree decompositions.

*Linearisation:* We begin by describing the alternative (b) in more detail. A *linear preorder* is a binary relation that is transitive and total (every two elements are related in at least one direction). In other words, this is a partition of a set into parts, and a linear order on these parts, as in the following example:

$$ \{1,2\} < \{3\} < \{4,5,6\} < \{7\}. $$

**Definition III.1 (Linearisation).** A linearisation of a tree decomposition is a linear preorder on its vertices such that vertices from the same part of the order are introduced in the same node of the tree decomposition.

We will be interested in linearisations which are consistent with the structure of the underlying graph. This is formalized by the *width* of the linearisation, which is defined to be the maximal rank of the prefixes of the preorder, i.e. downward closed sets. We say that a class of tree decompositions has *linearisations of bounded width* if to each tree decomposition one can associate a linearisation, such that corresponding widths are bounded.

We are now ready to present the main lemma in our proof, which we call the Dichotomy Lemma.

**Lemma III.2 (Dichotomy Lemma).** Let $\mathcal{T}$ be a class of tree decompositions of bounded width, such that the local sub-decompositions have linearisations of bounded width. Then $\mathcal{T}$ either

<footnote n="3">³The rank in the above definition is functionally related to, but not identical, to the rank as defined by Oum and Seymour [22]. This is the number of linearly independent rows in a certain matrix, while our rank counts the number of distinct rows in the same matrix. These are not the same numbers, but one is bounded by a function of the other. A more detailed comparison of equivalent notions of rank can be found in [7].</footnote>
(a) transduces all trees; or

(b) has linearisations of bounded width.

When proving the first alternative, we will pay attention to the kind of transduction that is used. The details are presented in the appendix, but we remark here that the transductions are designed to enable future work regarding vertex minors and first-order transductions (see conclusion). The main theorem of this paper is an immediate corollary of the Dichotomy Lemma.

*Proof of Theorem I.1 using Lemma III.2.* Consider a class of graphs. Let $\mathcal{T}$ be the corresponding tree decompositions from Lemma II.10. The local sub-decompositions have trivial linearisations of bounded width, where the two parts are the two children of a node. Therefore, we can apply the Dichotomy Lemma. In the first case, the class transduces all trees. In the second case, the linearisations are total orders (since each node introduces at most one vertex), and therefore they witness bounded linear cliquewidth by the linear version of Lemma II.10. □

The rest of this paper is devoted to proving the Dichotomy Lemma. Here is the overall strategy. In Section IV, we identify a special kind of tree decompositions, which are called uniform, and we show that the Dichotomy Lemma can be reduced to the uniform case. The idea behind uniform tree decompositions is that all nodes and contexts behave similarly in a uniform tree decomposition. Next, in Section V, we prove the Dichotomy Lemma for uniform tree decompositions.

## IV. UNIFORM TREE DECOMPOSITIONS

In this section, we define uniform tree decompositions, and reduce the Dichotomy Lemma to such decompositions.

The most basic property of uniform tree decompositions is that all nodes have the same number of colours $k$. Therefore, for a uniform tree decomposition, we can refer to the set of colours without needing to specify a node.

A more important property of uniform tree decompositions is that the $q$-theories, as defined in Section II-C, are similar across the decomposition, for some suitably chosen quantifier depth $q$. Let us describe this similarity in more detail. First, we will want all nodes to have the same $q$-theory, which means that for all nodes, the corresponding induced subgraph has the same $q$-theory. This assumption can be easily achieved by a variant of the pigeonhole principle. However, apart from nodes, will also want the $q$-theory to be similar for connections between nodes; this notion is more complicated and explained in the following section.

### A. Forward invariance

When comparing the theories of two nodes, we will mainly care about directly comparable nodes. Define a context in a tree to be a pair of nodes $X \subset Y$, such that one is strictly contained in the other. To each context we can associate a unary graph term. In this graph term, we only have the vertices from $Y \setminus X$, plus additional vertices (the ports) that

represent the colours of the induced subgraph of $X$. Since we will assume that all nodes have the same number of colours $k$, the type of this unary graph term will be $k \to k$, which means that it has $k$ colours (representing the colours of $Y$), one argument, and $k$ ports in that argument (representing the colours of $X$). We define the $q$-theory of the context $X \subset Y$ to be the $q$-theory of the corresponding unary graph term. The corresponding structure has $k$ constants for the ports, and $k$ unary relations for the colours.

Ideally, we would like all contexts in the tree decomposition to have the same $q$-theory. Unfortunately, this is infeasible, and we will have to settle for a weaker property, which we call forward invariance, and define below. This property will be guaranteed by an application of a theorem of Colcombet [9], which can be seen as a tree version of the Factorisation Forest Theorem [27].

**Definition IV.1 (Forward invariance).** Consider a tree decomposition where all nodes have $k$ colours. We say that this tree decomposition has forward invariant $q$-theories if

$$ (q\text{-theory of } E) \circ (q\text{-theory of } F) = (q\text{-theory of } E) $$

holds for all unary graph terms $E$ and $F$ that arise from contexts in the tree decomposition.

Observe that by compositionality (5), the $q$-theory in the above equation is also the same as the $q$-theory of $E \circ F$. Intuitively speaking, the theory of the left unary graph term (which is the one whose corresponding operation is applied later, i.e. it is the external one in the composed term) dominates the theory of the right one. Observe that we do not assume that $E$ and $F$ arise from consecutive contexts $X \subset Y \subset Z$ in the tree.

One important consequence of forward invariance is that all $q$-theories are idempotent, i.e. they satisfy $\tau \circ \tau = \tau$.

### B. Supercolours

Another difficulty with tree decompositions is that the colour of a vertex is relative to the choice of a node that contains it. We will use the following notation for disambiguation: if $X$ is a node in a tree decomposition, and $a$ is a colour, then we write $X.a$ for the vertices that have colour $a$ in the induced subgraph of $X$. Consider a context $X \subset Y$ in a tree decomposition. An immediate corollary of the definition of tree decompositions is that for every colour $a$ used by the node $X$ there is a unique colour $b$ that is used by the node $Y$ such that $X.a \subseteq Y.b$. The function that maps $a$ to $b$ is called the *recolouring* of the context. In a similar way, we can associate a recolouring to a unary graph term, and we have the homomorphism property:

$$ \text{recolouring of } E \circ F = (\text{recolouring of } E) \circ (\text{recolouring of } F). $$

As we have observed, if the $q$-theories are forward invariant, then they are idempotent. Since the recolouring of a unary graph term $E$ is already seen in its $q$-theory for quantifier depth $q = 0$, it follows that all recolourings are idempotent as well. We will be interested in the *kernel* of a recolouring,
i.e. an equivalence class of the relation which identifies two colours if they are recoloured to the same colour.

**Lemma IV.2.** Let $q \in \{0, 1, \dots\}$. Consider a tree decomposition in which the $q$-theories are forward invariant. Then all recolourings have the same kernel.

We have a name for the equivalence classes of the kernel, when the conclusions of the above lemma are satisfied.

**Definition IV.3** (Supercolours). We say that a tree decomposition has supercolours if the recolourings of all contexts are idempotent and have the same kernel. In such a case, a supercolour is defined to be an equivalence class of this kernel.

The salient property of supercolours is that they do not change throughout a decomposition: if a vertex has super-colour $A$ in some node, then it has supercolour $A$ in all nodes. From now on, when we talk about supercolours of a tree decomposition, we implicitly assume that the assumptions of the above definition are satisfied. For example, this will be the case as long as the quantifier-free theories of contexts are forward invariant.

### C. Colour connectedness

We now describe another property that will be assumed in uniform tree decompositions, which is about connectivity. For a connected component of the underlying graph in a tree decomposition, we say that it *touches all colours* in a node $X$ if the connected component has nonempty intersection with $X.a$ for every colour $a$. If a connected component is such that for all nodes, the component does not touch all colours, then we can restrict the tree decomposition to the component, and have strictly smaller width. This will allow us to call the induction assumption in the Dichotomy Lemma, since we will prove it by an induction on the width. Therefore, the interesting connected components will be those that touch all colours in some node<fnref n="4" />.

The above discussion uses connected components. However, since we are dealing with dense graphs, the properties that we consider should be stable under complementing the edge relation, and therefore co-connectivity should be equally important as connectivity. To formalize such stability, we use flips, which also played a prominent role in the analysis of linear cliquewidth from [6, p. 5:14].

**Definition IV.4** (Colour flip). For a $k$-coloured graph and two not necessarily distinct colours $a, b \in \{1, \dots, k\}$, define the *ab-flip* to be the graph which has the same vertices and colours, and where the edge relation is obtained by taking the symmetric difference of the original edge relation with the set

$$ \{vw | v \text{ has colour } a \text{ and } w \text{ has colour } b\}. $$

A graph obtained by applying a sequence of operations of this kind is called a colour flip of the original graph.

We will mainly flip entire supercolours, in the following sense. Consider a tree decomposition which has supercolours. For two supercolours $A$ and $B$, define the *AB-superflip* to be the result of doing all *ab-flips* with $a \in A$ and $b \in B$. The order of these flips is irrelevant to the outcome.

We are now ready to formalise a connectivity assumption that will be used in uniform tree decompositions: we want some connected component to touch all colours in some node, even after doing superflips.

**Definition IV.5** (Colour connected). Consider a tree decomposition which has supercolours. We say that it is colour connected if after every sequence of superflips, there is some connected component of the underlying graph and some node such that the component touches all colours in the node.

### D. Uniform tree decompositions

We have now defined all notions that will be collected in the definition of uniform tree decompositions.

**Definition IV.6** (Uniform tree decomposition). A tree decomposition is called uniform for quantifier depth $q$ if:

1) The $q$-theories of nodes are all the same;

2) The $q$-theories of contexts are forward invariant;

3) It is colour connected.

When we talk about uniformity and do not specify the quantifier depth $q$, then we mean $q = 9$. This is because quantifier depth 9 will be enough for all reasonings that we use in the proof.

The above definition refers to individual tree decompositions. We will also talk about uniformity for a class of tree decompositions. Such a class is called uniform if all tree decompositions in it are uniform, and furthermore the theories are the same across the class, in the following sense. For item 1, there is only one theory in each tree decomposition, so we want this theory to be the same across the class. For item 2, we want the sets of possible theories of contexts to be the same across the class.

The following lemma shows that the Dichotomy Lemma reduces to the uniform case. The main ingredient in the proof is the tree version of factorisation forests that was proved by Colcombet [9].

**Lemma IV.7.** If the Dichotomy Lemma holds for uniform classes of tree decompositions, then it holds for all classes.

Let us finish this section with the following lemma, which shows that we can apply superflips at will when proving the Dichotomy Lemma for uniform classes.

**Lemma IV.8.** Consider a class of tree decompositions which has supercolours. Performing a superflip does not affect:

1) being uniform;

2) having bounded linear cliquewidth;

3) transducing all trees.

<footnote n="4">⁴It would be tempting to remove all other connected components. We will, however, need to allow connected components that do not touch all colours, since deleting them could violate other assumptions that we work with, mainly forward invariance of theories. Therefore, we will only require that at least one connected component touches all colours.</footnote>
V. THE DICHOTOMY LEMMA FOR UNIFORM CLASSES

This section proves the Dichotomy Lemma for uniform
classes, thus completing the proof of the main theorem.

A. Local edges

We begin with a special case, where edges from the
underlying graph can only connect nearby nodes in the tree
decomposition, as formalised in the following definition.

**Definition V.1** (Local edges). *Two nodes in a tree are called nearby if they are equal to each other, or they are siblings, or one is a child of the other. An edge in a tree decomposition is called local if its endpoints are introduced in adjacent nodes.*

We first show that the Dichotomy Lemma holds when all
edges are local, which roughly corresponds to the case of
stable bounded cliquewidth as in [16].

**Lemma V.2.** *The Dichotomy Lemma holds for uniform classes of tree decompositions where all edges are local.*

The proof of the above lemma is long and relegated entirely
to the appendix. Intuitively speaking, tree decompositions
that have only local edges are amenable to similar tech-
niques as treewidth decompositions. Therefore, the proof of
Lemma V.2 is somewhat similar to the proof that graphs of
bounded treewidth have definable tree decompositions [8].
In fact, our proof of Lemma V.2 could be used, with minor
extensions, to get a new and better structured proof of the
result from [8].

We would also like to remark that under the local edge
assumption, we get a slightly stronger conclusion than the
one in the Dichotomy Lemma: we prove that either the
class has bounded linear cliquewidth, or otherwise all acyclic
graphs can be found using a special kind of transduction,
namely vertex deletions and a bounded number of indepen-
dent contractions (these are defined in the appendix).

This completes the discussion of the case where all edges
are local.

B. *Entanglement and normalisation*

The rest of this section is devoted to proving the Di-
chotomy Lemma for uniform classes that have at least one
non-local edge. In our proof, a crucial role will be played
by the analysis of a relation on supercolours, which we call
entanglement, and define in this section. The intuitive idea
is that entangled supercolours can be used to generate the
half-graphs that were described in Example 3.

Consider a uniform tree decomposition. A colour is called
*transient* if it does not belong to the image of any recolouring
used by (some context in) the tree decomposition. A transient
colour can only be used once, in the following sense: if a
vertex is introduced in a node *X*, then it can have a transient
colour in *X*, but not in any other node, because by the
time the other node is reached, a recolouring will have been
applied. The non-transient colours are called *fixpoint* colours.
This is because all recolourings are idempotent, and if a

colour *a* belongs to the image of an idempotent recolouring
*e*, then it is a fixpoint, i.e. *a* = *e*(*a*).

We are now ready to define entanglement. Recall that port
*a* in a context *X* ⊂ *Y* is defined to be the set of vertices *X*a.

**Definition V.3 (Entanglement).** *Consider a uniform tree
decomposition. We say that supercolour *A* is entangled with
supercolour *B*, denoted by *A* × *B*, if we have both:*

(a) for every context $X \subset Y$ and every fixpoint colour $b \in B$, there is an edge from supercolour $A$ in $Y \setminus X$ to port $b$;

(b) for every context $X \subset Y$ and every fixpoint colour $a \in A$, there is a non-edge from supercolour $B$ in $Y \setminus X$ to port $a$.

Here is a picture of entanglement, which explains the
choice of the symbol ×, and the similarity to half-graphs:

<figure><img src="image_10.png" /></figure>

The dotted lines indicate that there could be an edge or not.
The only information about the edges that is known concerns
the diagonals: one of them is an edge, and the other one is
not. It is not even really meaningful to speak about the right
vertical dotted line as being edge, because a port represents
a set of vertices, and therefore the connection between two
ports is not necessarily well-defined.

Entanglement is not necessarily symmetric, i.e. we could
have *A* × *B* but not *B* × *A*. Also, when speaking of en-
tanglement, we do not assume that *A* is different from *B*,
i.e. it could be the case that there is self-entanglement *A* × *A*.
Eventually, we will show that for interesting tree decomposi-
tions, entanglement is actually symmetric and irreflexive, and
therefore it can be seen as an undirected graph where the
vertices are supercolours. For the moment, however, we will
need to specify the order between *A* and *B* when speaking
of entanglement.

*Normalisation:* We now show that for non-entangled
pairs of supercolours, edges connecting them are local, at
least up to taking superflips.

**Lemma V.4.** (Normalisation Lemma). *To every uniform tree
decomposition one can apply a sequence of superflips so that
the resulting tree decomposition has the following property:*

(*) For every two supercolours *A* and *B*, possibly equal to
each other, we have either:

a) one of the entanglements $A \times A$, $B \times B$, $A \times B$ or $B \times A$ holds; or

b) if we restrict the tree decomposition to supercolours $A \cup B$, then all edges are local.

We give a name to the conclusion of the above lemma.
**Definition V.5 (Normalized tree decomposition).** A uniform tree decomposition is called normalized if it satisfies condition (*) from the Normalisation Lemma.

By the Normalisation Lemma, every uniform tree decomposition can be made normalised by applying superflips. Since superflips affect neither the assumptions nor conclusions of the Dichotomy Lemma by Lemma IV.8, we can assume that all tree decompositions are normalised. The rest of this section is devoted to proving the Dichotomy Lemma for uniform classes of tree decompositions that contain only normalised tree decompositions.

If there is no entangled pair of supercolours, then the Normalisation Lemma tells us that all edges are local, and therefore we can use Lemma V.2 to get the conclusion of the Dichotomy Lemma. Therefore, we can assume that there is at least one entangled pair.

Summing up, we are left with proving the Dichotomy Lemma for classes of tree decompositions which are normalised, and contain at least one entangled pair of supercolours. This is the purpose of the rest of this section.

### C. Orientations

In the proof, we will progressively identify a linear order in the tree decompositions, and we will show that any deviation from this linear order will make it possible to transduce all trees. In the first step toward defining this order discipline, we will study connections between disjoint nodes. We will show that if the class does not transduce all trees, such connections must necessarily result in some orientation of the entanglement relation, with orientations defined as follows.

**Definition V.6 (Orientation).** An orientation for a uniform tree decomposition is a binary relation $\rightarrow$ on its supercolours such that for every supercolours A and B, possibly equal, we have:

1) if $A \times B$ then exactly one of $A \rightarrow B$ or $B \rightarrow A$ holds;

2) if $A \times B$ does not hold, then neither $A \rightarrow B$ nor $B \rightarrow A$.

The following straightforward fact, whose main purpose is clarifying the definition above, shows that an orientation can only arise if the entanglement relation is an undirected graph (in which case it corresponds to the usual notion of orientation for an undirected graph).

**Fact V.7.** An orientation is only possible if the entanglement relation is symmetric and irreflexive.

We will be mainly interested in tree decompositions where every choice of disjoint nodes and recolourings leads to an orientation, as described in the following definition. In the definition, we will care about connections to fixpoint colours.

**Definition V.8 (Oriented tree decomposition).** We say that a uniform tree decomposition is oriented if for every:

* disjoint nodes $X_1$ and $X_2$; and

* recolourings $e_1$ and $e_2$ that appear in some contexts of the tree decomposition,

the following binary relation on supercolours is an orientation:

$$A \rightarrow B \stackrel{\text{def}}{=} \text{there is an edge from } X_1 \cdot e_1(A) \text{ to } X_2 \cdot e_2(B).$$

For an oriented tree decomposition, we will use the name orientation of $(X_1, e_1)$ and $(X_2, e_2)$ for the orientation that is described in the above definition. Ideally, we would like the orientation to depend only on the nodes $X_1$ and $X_2$, and not on the recolourings $e_1$ and $e_2$. Eventually, we will show that this is indeed the case for interesting tree decompositions. This, however, will require a substantial amount of work, and will only be observed after we have finished the entire proof. Therefore, for the moment we will have to work with tree decompositions where all four parameters (two disjoint nodes and two recolourings) are needed to specify an orientation.

The following lemma reduces to the oriented case.

**Lemma V.9.** (Orientation Lemma). In order to prove the Dichotomy Lemma, it is enough to prove it for uniform classes of tree decompositions which:

1) do not transduce all trees;

2) contain at least one entangled pair of supercolours;

3) have unbounded Strahler number;

4) contain only normalized tree decompositions;

5) contain only oriented tree decompositions.

*Proof intuition.* The long proof of the lemma is in the appendix. Let us only give some intuition about it, by describing one of its aspects, namely self-entanglement. One of the consequences of orientations is that there cannot be any supercolour A that is entangled with itself. Let us give a brief sketch of the following fact: if some supercolour is entangled with itself, and the tree decompositions have unbounded Strahler number, then all trees can be transduced.

Consider some supercolour A that is entangled with itself. Using an extraction process, one can find sub-decompositions which have unbounded Strahler number, and where all contexts use the same recolouring e. Let $a = e(A)$ be the fixpoint colour that corresponds to supercolour A under this recolouring. For every disjoint nodes $X_1$ and $X_2$ in such a tree decomposition, we have either:

(a) an edge from $X_1 \cdot a$ to $X_2 \cdot a$; or

(b) a non-edge from $X_1 \cdot a$ to $X_2 \cdot a$.

Using another extraction process, one can also assume without loss of generality that the choice of (a) or (b) is always the same and does not depend on the disjoint nodes. The proof is the same for both choices, so we assume (b). By the assumption that A is entangled with itself, we know that for every context $X \subset Y$ there is an edge from colour A in $Y \setminus X$ to port $X \cdot a$. (There is also some non-edge, which is used in the case of (b).) Using these edges and a further extraction process, we can find sub-decompositions of unbounded Strahler number, where the underlying tree is a binary tree, and for every node, there is a special vertex that is introduced in this node with the following properties:
<figure><img src="image_11.png" /></figure>

If we only keep the special vertices, then the corresponding induced subgraph will be a *comparability tree*, i.e. a graph obtained from a tree by having edges which represent “ancestor or descendant”, as in the following picture:

<figure><img src="image_12.png" /></figure>

From comparability trees, one can transduce all trees. This can even be done using first-order logic. □

The five conditions from the above lemma will be referred to as the conditions from the Orientation Lemma. We will eventually prove that if a class satisfies these conditions, then applying the Dichotomy Lemma will necessarily yield linearisations of bounded width. This will complete the proof of the Dichotomy Lemma, and thus also of the main theorem.

### D. Bipolar orientations

From now on, we only work with classes of tree decompositions satisfying the conditions from the Orientation Lemma.

Consider a tree decomposition in such a class. By definition of oriented tree decompositions, for every disjoint nodes $X_1$ and $X_2$, and for every recolourings $e_1$ and $e_2$, there is some orientation on the entanglement graph that corresponds to $(X_1, e_1)$ and $(X_2, e_2)$. We will eventually show that (a) there are only two possible orientations, and (b) the orientation depends only on the nodes $X_1$ and $X_2$ and not on the recolourings $e_1$ and $e_2$. This will allow us to orient any two nodes as $X_1 \to X_2$ or $X_1 \leftarrow X_2$, depending on the direction of the orientation, and will ultimately lead to a linear pre-order on the nodes and vertices of the tree decomposition. This section is devoted to property (a). We begin by giving a name to this property. In the following definition, the *opposite* of an orientation is obtained by swapping the directions of all edges.

**Definition V.10 (Bipolar orientations).** We say that a uniform class of tree decompositions has bipolar orientations if there is some orientation $\to$ such that for every pair of disjoint nodes $X_1$ and $X_2$ and every recolourings $e_1$ and $e_2$ from the class, the orientation of $(X_1, e_1)$ and $(X_2, e_2)$ exists, and is either $\to$ or its opposite.

For the moment, whether the orientation is $\to$ or its opposite could depend on the choice of recolourings. The following lemma shows that oriented classes must be bipolar.

**Lemma V.11.** (Bipolar Lemma). If a uniform class of tree decompositions satisfies the conditions from the Orientation Lemma, then it has bipolar orientations.

*Proof intuition.* Similarly to the Orientation Lemma, we only have space to convey some brief intuition. The idea is that any violation of bipolar orientations can be used to transduce all trees. This is because such a violation will lead to certain patterns that appear in some context, and therefore – by uniformity – in all contexts. Using these patterns, one can extract sub-decompositions where the underlying trees are binary and have unbounded Strahler number, such that in every node we can find a certain obstructing binary term, from a finite list of obstructions. The obstructions are designed so that their iterations can transduce all trees. Here is one of them:

<figure><img src="image_13.png" /></figure>

If we iterate the above obstruction, then we get a half-graph, together with certain synchronising vertices (the vertex that is introduced by the term), which can be used to recover intervals in the half-graph ordering that correspond to subtrees in the tree decomposition. Again, the corresponding transduction can be done using first-order logic; this is the case for all obstructions. □

### E. Consistent cuts

Thanks to the Bipolar Lemma, we know that the class has bipolar orientations. In this section, we show that such orientations can be used to impose a certain amount of order on the vertices introduced by a context. By a “certain amount of order” we mean that we can place some vertices on the left, and some vertices on the right, as described in the following definition.

**Definition V.12 (Consistent cut).** Consider a uniform tree decomposition, and a subset $U$ of vertices, which might not be a node. A cut of this subset is defined to be a partition of $U$ into two parts, called the left and right parts. A cut is called consistent with an orientation $\to$ if the equivalence

$$vw \text{ is an edge} \iff (\text{supercolour of } v) \to (\text{supercolour of } w) \qquad (6)$$

holds for every $v$ in the left part and every $w$ in the right part.

We will be mainly interested in a special case when $U$ arises from a context. Define the *interior* of a node $X$, denoted by $\langle X \rangle$, to be the vertices whose connected component in the graph induced by $X$ contain at least one non-local colour.
**Definition V.13** (Consistent cut for a context). Consider a context $X \subset Y$ in a uniform tree decomposition. A cut of

$$U = \langle Y \rangle \setminus \langle X \rangle$$

is consistent with an orientation $\rightarrow$ and a recolouring $e$ if:

1) the cut is consistent with the orientation $\rightarrow$ as in Definition V.12; and

2) for every vertex $v \in U$ with supercolour $A$, we have:

a) if $A \rightarrow B$, then $v$ is in the left part if and only if it has an edge to $X.e(B)$;

b) if $A \leftarrow B$, then $v$ is in the right part if and only if it has an edge to $X.e(B)$.

We now explain that the cut from the definition is essentially unique. Indeed, the two implications in the above definition determine uniquely the side of the cut for vertices that have non-local colours. This in turn determines uniquely the side for vertices with local colours which admit a path to some vertex with a non-local colour, because the notion of cut forbids local edges to cross sides. The only remaining vertices are those from connected components of $U$ which use only local colours; these can be placed on either side of the cut. Summing up, up to choosing sides for connected components of $U$ that have only local colours, the cut from the above definition is unique, if it exists. The main issue, however, is whether this cut does indeed exist. The following lemma gives a positive answer, and shows that this happens for every recolouring and every context in every tree decomposition.

**Lemma V.14.** (Consistent Cut Lemma) Consider a uniform class of tree decompositions that satisfies the conditions from the Orientation Lemma. Let $\rightarrow$ be one of the two orientations from the Bipolar Lemma. Then for every context, and every recolouring $e$, the context has a cut that is consistent with $\rightarrow$ and $e$.

*Proof intuition.* Similarly to the Bipolar Lemma, this proof uses an exhaustive analysis of the obstructions that arise from a violation of consistent cuts. Let us only give an example of one of these (finitely many) obstructions:

<figure><img src="image_14.png" /></figure>

Similarly to the obstruction that was discussed for the Bipolar Lemma, we have two half-graph orders, which together with extra synchronising vertices that can be used to recover the tree structure. As usual, the transduction uses first-order logic only. □

## F. Proof of the Dichotomy Lemma

We now present the last step of the proof of the Dichotomy Lemma. By the Orientation Lemma, it is enough to consider classes that satisfy the corresponding conditions.

**Lemma V.15.** The Dichotomy Lemma holds for classes of tree decompositions that satisfy the conditions from the Orientation Lemma.

*Proof intuition.* We will show that, under the conditions from the Orientation Lemma, the class will have linearisations of bounded width. Thanks to the Bipolar Lemma, there is essentially only one orientation $\rightarrow$ that is possible. Thanks to the Consistent Cut Lemma, for every context $X \subset Y$, one can cut the vertices introduced in this context into left and right parts, such that the edges from the left part to the right part follow a very strict discipline that depends only on the supercolours of the endpoints. If we take the special case where $Y$ is the root node, this means that the complement of each node $X$ is cut into a left and right part. One then shows that these cuts are compatible with each other across different choices of $X$, and therefore they can be stitched together to get a linearisation of bounded width. □

# VI. CONCLUSIONS

We have shown that if the linear cliquewidth is unbounded, then all trees are transduced. A related conjecture is that if linear cliquewidth is unbounded, then all trees can be obtained as vertex minors [18, Conjecture 1.1]. Our proof shows that if all trees are transduced, then this is done by using a finite number of obstructions. Therefore, the conjecture is reduced to studying each of the obstructions; we would like to investigate this in the future.

Another related conjecture [16, Conjecture 3] is that classes with unbounded linear cliquewidth should transduce, in first-order logic, classes that contain subdivisions of all trees. We believe that our insights may lead to a proof of this conjecture, since the obstructions can be transduced in first-order logic, up to subdividing paths. We leave the details to a future version of this paper.

Another direction for future work is to find definable tree decompositions. We hope that the techniques developed in this paper can be used to show that if a class of graphs has bounded cliquewidth, then there is an MSO transduction that outputs a tree decomposition for each graph in the class. This would be a dense analogue of a similar result for treewidth that was proved in [8]; for more consequences of this conjectured result, see [4], [7].

# REFERENCES

[1] Stefan Arnborg, Jens Lagergren, and Detlef Seese. Problems easy for tree-decomposable graphs extended abstract. In Timo Lepistö and Arto Salomaa, editors, *Automata, Languages and Programming*, pages 38–51, Berlin, Heidelberg, 1988. Springer Berlin Heidelberg.

[2] Achim Blumensath and Bruno Courcelle. On the Monadic Second-Order Transduction Hierarchy. *Logical Methods in Computer Science*, Volume 6, Issue 2, June 2010.
[3] Hans L. Bodlaender. A linear time algorithm for finding tree-decompositions of small treewidth. In *Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing*, STOC '93, pages 226–234, New York, NY, USA, 1993. Association for Computing Machinery.

[4] Mikolaj Bojanczyk. The category of MSO transductions. *CoRR*, abs/2305.18039, 2023.

[5] Mikolaj Bojańczyk. Folding interpretations. In *Logic in Computer Science*, LICS '22. Association for Computing Machinery, 2023.

[6] Mikolaj Bojańczyk, Martin Grohe, and Michal Pilipczuk. Definable decompositions for graphs of bounded linear clique-width. *Logical Methods in Computer Science*, Volume 17, Issue 1, January 2021.

[7] Mikolaj Bojańczyk and Pierre Ohlmann. Rank-decreasing transductions. In *LICS*, 2024.

[8] Mikolaj Bojańczyk and Michal Pilipczuk. Definability equals recognizability for graphs of bounded treewidth. In Martin Grohe, Eric Koskinen, and Natarajan Shankar, editors, *Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS '16, New York, NY, USA, July 5-8, 2016*, pages 407–416. ACM, 2016.

[9] Thomas Colcombet. A Combinatorial Theorem for Trees. In *International Colloquium on Automata, Languages and Programming, ICALP, Wroclaw, Poland*, Lecture Notes in Computer Science, pages 901–912. Springer, 2007.

[10] Bruno Courcelle. The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. *Information and Computation*, 85(1):12–75, March 1990.

[11] Bruno Courcelle. The monadic second-order logic of graphs v: on closing the gap between definability and recognizability. *Theoretical Computer Science*, 80(2):153–202, 1991.

[12] Bruno Courcelle and Joost Engelfriet. A logical characterisation of the sets of hypergraphs defined by hyperedge replacement grammars. *Mathematical Systems Theory*, 28(6):515–552, 1995.

[13] Bruno Courcelle and Joost Engelfriet. *Graph Structure and Monadic Second-Order Logic - A Language-Theoretic Approach*, volume 138 of *Encyclopedia of Mathematics and Its Applications*. Cambridge University Press, 2012.

[14] Bruno Courcelle and Sang-il Oum. Vertex-minors, monadic second-order logic, and a conjecture by seese. *Journal of Combinatorial Theory, Series B*, 97(1):91–126, 2007.

[15] Joost Engelfriet. A characterization of context-free nce graph languages by monadic second-order logic on trees. In Hartmut Ehrig, Hans-Jörg Kreowski, and Grzegorz Rozenberg, editors, *Graph Grammars and Their Application to Computer Science*, pages 311–327, Berlin, Heidelberg, 1991. Springer Berlin Heidelberg.

[16] Jakub Gajarský, Michal Pilipczuk, and Szymon Torunczyk. Stable graphs of bounded twin-width. *CoRR*, abs/2107.03711, 2021.

[17] Jim Geelen, Bert Gerards, and Geoff Whittle. Excluding a planar graph from gf (q)-representable matroids. *Journal of Combinatorial Theory, Series B*, 97(6):971–998, 2007.

[18] Mamadou Moustapha Kanté and O-joung Kwon. Linear rank-width of distance-hereditary graphs ii. vertex-minor obstructions. *European Journal of Combinatorics*, 74:110–139, 2018.

[19] Donggyu Kim and Sang-il Oum. Vertex-minors of graphs: A survey. *Discrete Applied Mathematics*, 351:54–73, 2024.

[20] Leonid Libkin. *Elements of finite model theory*, volume 41. Springer, 2004.

[21] Maryanthe Malliaris and Saharon Shelah. Regularity lemmas for fixpoint graphs. *Transactions of the American Mathematical Society*, 366(3):1551–1585, 2014.

[22] Sang-il Oum and Paul D. Seymour. Approximating clique-width and branch-width. *J. Comb. Theory B*, 96(4):514–528, 2006.

[23] Neil Robertson and Paul D. Seymour. Graph minors. i. excluding a forest. *J. Comb. Theory B*, 35(1):39–61, 1983.

[24] Neil Robertson and Paul D Seymour. Graph minors. v. excluding a planar graph. *Journal of Combinatorial Theory, Series B*, 41(1):92–114, 1986.

[25] Detlef Seese. The structure of the models of decidable monadic theories of graphs. *Annals of pure and applied logic*, 53(2):169–195, 1991.

[26] Saharon Shelah. The Monadic Theory of Order. *Annals of Mathematics*, pages 379–419, 1975.

[27] Imre Simon. Factorisation forests of finite height. *Theoretical Computer Science*, 72(1):65–94, 1990.

[28] Imre Simon. Factorisation forests of finite height. *Theoret. Comput. Sci.*, 72(1):65–94, 1990.

In this part of the appendix, add some clarifications, extra material, and missing proofs for the results from the preliminaries.

### A. Terms and regular classes of graphs

In this part of the appendix, we describe regular classes of graphs. These are graphs that are obtained by iterating a single term operation. In the proof of the Dichotomy Lemma, when trees will be transduced, the transduction will always pass through such a class. This will mean that certain regular repeating patterns can be identified in every graph of large linear clique-width.

**Term operations:** We begin by disambiguating the notion of term operation in the clique-width algebra. One of the points that need clarification is that we do not allow copying of arguments, unlike the usual notion of term operation in universal algebra. The set of term operations has an inductive definition. Every basic operation is a term operation. If we have an already defined term operation of type

$$k_1 \times \cdots \times k_n \to k,$$

and for some argument $i \in \{1, \dots, n\}$ we have another already defined term operation of type

$$\ell_1 \times \cdots \ell_m \to k_i,$$

then we can compose them to get a new term operation of type

$$k_1 \times \cdots \times k_{i-1} \times \ell_1 \times \cdots \ell_m \times k_{i+1} \times \cdots \times k_n \to k.$$

**Templates and regular classes:** We are now ready to describe the regular classes that were mentioned at the beginning of this section.

**Definition A.1 (Template and regular class).** A template with $k$ colours consists of:

1) an initial graph with $k$ colours; and

2) a binary graph term of type $k \times k \to k$.

The class of graphs generated by a template is the least class of $k$-coloured graphs that contains the initial graph, and which is closed under applying the (operation corresponding to the) binary graph term. A class of graphs is called regular if it is generated by one template.

Many interesting phenomena can be observed already in such classes, and in fact our proof of the main theorem will show that every class can be reduced (the reduction is called covering, and is defined in Section I) to one of finitely many regular graph classes.

Let us discuss some examples of regular classes of graphs, and how they relate to trees.

**Example 4.** [Comparability tree] For a tree, define is *comparability graph* as follows. (This graph is also used in the main body of the paper, in the proof intuition for the Orientation
Lemma.) The vertices are the nodes of the tree, and the edge relation connects nodes that are related by the descendant relation in either way. Here is a picture:

<figure><img src="image_15.png" /></figure>

The tree order can be recovered from the comparability graph as follows: a vertex $v$ is an ancestor of a vertex $w$ if and only if

$$vu \text{ is an edge} \Rightarrow wu \text{ is an edge}$$

holds for every vertex $u$ that is neither $v$ nor $w$. Therefore, the comparability graphs transduce all trees, and in particular they have unbounded cliquewidth.

Here is a template with one colour that generates comparability graphs of binary trees:

<figure><img src="image_16.png" /></figure>

The binary operation inputs two graphs, takes their disjoint union without any edges between them (because there is no edge connecting the arguments), and adds a new vertex (corresponding to the introduced vertex) that is connected by edges to the two graphs (because there is an edge from the introduced vertex of the template to both ports). Therefore, this template will generate all comparability graphs of binary trees. □

**Example 5.** [Child tree] In the previous example, the graph edges in the output corresponded to the descendant/ancestor relation in a tree. Let us now design a template that generates trees in the usual way, with edges corresponding to the child/parent relation. The template will have two colours. One colour (in blue) is used to temporarily store the root vertex, and the other colour (in red) is used to store the remaining vertices. Here is the template:

<figure><img src="image_17.png" /></figure>

Observe that the binary operation uses a non-trivial recolouring: the blue vertices of its input become red after applying the binary operation. Ideally, the initial graph would have only one vertex in the blue colour, but we need the colouring to be surjective, hence the extra two red vertices. □

The template in the above example is the only template from this paper that uses a non-trivial recolouring.

**Example 6.** In the above two examples, the tree structure of the input tree was visible in the generated template. This is not necessarily the case for all templates. Consider the following three alternatives to the binary operation in the comparability tree template in Example 4:

<figure><img src="image_18.png" /></figure>

For the first alternative, the generated graphs have no edges. For the second and third alternative, the generated graphs will consist of disjoint unions of cliques. □

**Example 7.** [Half-graph] Recall the half-graphs from Example 3. Here is a template that generates half-graphs:

<figure><img src="image_19.png" /></figure>

There are other ways as well. For example, we could replace the binary operation by any of the following two binary operations:

<figure><img src="image_20.png" /></figure>

<figure><img src="image_21.png" /></figure>

We will be interested in regular classes that transduce all trees, such classes will be called *regular branching classes*.

### B. Splits

In the proof, we will use a tree extension of Simon's Factorisation Forest Theorem [28] that was proved by Colcombet [9]. The purpose of this section is to present necessary definitions for this result.

The idea is to hierarchically decompose a tree into layers, such that on each layer the tree behaves in a uniform way with respect to some semigroup operation. Such a decomposition is called a split, and is defined below.

**Definition A.2 (Splits and their layers).** For a tree, define a split to be a function from the nodes of the tree to some linearly ordered set (called the levels). We say that two nodes are visible in the split if they are related by the ancestor relation, they have the same value under the split, and there is no node with strictly bigger value between them. A layer of the split is a set
of nodes that is connected by the reflexive transitive closure of the visibility relation.

Observe that each layer is itself a minor of the original tree. The layers of a split are a partition of the tree (since they are obtained by taking the reflexive transitive closure of some relation). Here is a picture of a split with three examples of layers:

<figure><img src="image_22.png" /></figure>

Throughout this paper, we will be studying trees from the perspective of contexts, which are ordered pairs of nodes. Recall the notion of contexts, which is also defined in the main body of the paper: a *context* in a tree is pair of nodes $X \subset Y$ where one is strictly contained in the other.

The point of splits is to ensure that on each layer, all contexts are similar in some way. Define an *additive labelling*, see [9, Section 2.1] or [26, p. 384], to be a function that maps contexts in a tree to elements of some semigroup, in a way that is consistent with the composition:

$$ \text{label of } Z \supset X = (\text{label of } Z \supset Y) \cdot (\text{label of } Y \supset X). $$
semigroup operation

We think of the additive labelling as being produced by a top-down (i.e. root-to-leaves) procedure, which explains the order of the semigroup operation.

**Definition A.3 (Forward invariance).** Let $f$ be a function that maps contexts in a tree to some semigroup. We say that $f$ is forward invariant if $s \cdot t = s$ for all $s, t$ in the image of $f$.

This notion coincides with the forward invariance of the theories that appears in Definition IV.1 in the main body of the paper.

Forward invariance says that the image of $f$ is contained in what is called a *left-zero semigroup*, i.e. a semigroup that satisfies the equation $s \cdot t = s$. It is useful to think of the left-zero semigroup as being part of a bigger semigroup, which is not left-zero, since that will be the case in our applications. The idea behind forward invariance is that the dominating value is the one that is closer to the root, i.e. the one on the left of the multiplication. The point of using splits is to partition a tree into layers which are forward invariant with respect to a given additive labelling, as stated below.

**Theorem A.4.** [9, Theorem 1] Consider an additive labelling of contexts in a tree, which uses a finite semigroup $S$. Then there is a split of height at most $|S|$ which is forward invariant on every layer.

The semigroup itself is not necessarily left-zero; this is only the case for the sub-semigroups that arise by looking at individual layer.

Ideally, we would like to have a stronger property than forward invariance, namely we would like every layer to use a single element of the semigroup. (This is the case in the word case of the Factorisation Forest Theorem.) This is not always possible, but it can be achieved for certain properties, namely ideals. A subset $I$ of a semigroup is called an *ideal* if $s \in I$ implies $t \cdot s \in I$ for every semigroup element $t$. (This is strictly speaking a left ideal in the semigroup, but it is the only kind of ideal that we use, so we just call it an ideal.)

**Lemma A.5.** If a layer in a split is forward invariant with respect to some additive labelling using a semigroup $S$, then it is invariant with respect to every ideal $I \subseteq S$, i.e. either all contexts belong to the ideal, or all of them are outside it.

*Proof.* Suppose that $s, t$ are values of two contexts in the layer. Then we have

$$ \begin{array}{ccc} s \in I & \Rightarrow & t \cdot s \in I \\ \text{because } I \\ \text{is a left ideal} & & \text{because } t \cdot s = t \text{ by} \\ & & \text{forward invariance} \end{array} $$

□

### C. Strahler constraints

In the proof, we will frequently be extracting trees from larger trees. This will be done using Lemma A.7, which is described below.

Define a *disjoint pair* in a tree to be two nodes that are disjoint, i.e. none is an ancestor of the other. In our extraction property, we will be working with some constraint on disjoint pairs; our goal will be to ensure that either all or none of the disjoint pairs satisfy this constraint.

**Definition A.6 (Strahler constraint).** A Strahler constraint in a tree is a family $\mathcal{C}$ of disjoint pairs which is commutative

$$ (X, Y) \in \mathcal{C} \Leftrightarrow (Y, X) \in \mathcal{C} $$

and closed under moving down in the tree:

$$ (X, Y) \in \mathcal{C} \Rightarrow (X, Y') \in \mathcal{C} \quad \text{when } Y' \text{ is a descendant of } Y. $$

In the above definition, we only move $Y$ down in the tree, but by commutativity we can do the same for $X$.

The following lemma, which will be used several times in our proof, shows us that if we take a tree together with a Strahler constraint, then we can either extract a tree minor of large Strahler number that uses the Strahler constraint everywhere, or otherwise we can find a split of small height for which the Strahler constraint is not used within layers.

**Lemma A.7.** Consider a tree $T$ with a Strahler constraint. Then for every $n \in \{0, 1, 2, \dots\}$, either:
1) there is a tree minor which has Strahler number at least $n$, and such that every disjoint pair of nodes in this minor belongs to the Strahler constraint; or

2) there is a split of height $n$ such that on every layer, there is no disjoint pair from the Strahler constraint.

**Proof.** A simple extraction argument. Define a split as follows: to each node $X$ we associate the largest $n$ such that the subtree of $T$ rooted at $X$ satisfies the first item, with the inherited Strahler constraint. Consider a layer $S$ of this split, and a pair of $S$-siblings. If this pair would belong to the constraint, then the number associated to their parent in $S$ would be bigger. Therefore, on each level $S$ of this split, no disjoint pair belongs to the constraint. This completes the proof, since either the root node is mapped to $n$, thus satisfying the first condition, or otherwise we have the second condition. □

**Example 8.** Consider a tree $T$, and choose a subset of nodes, call them red nodes. We will show that there is either a tree minor of large Strahler number that uses only red nodes, or otherwise there is a split of small height such that on every layer, red nodes have at most one child. Define a Strahler constraint to consist of disjoint pairs $(X, Y)$ such that the node where they meet, i.e. the smallest node that contains both of them, is a red node. Apply Lemma A.7. A tree minor as in the first item is one in which every two nodes meet on a red node from the original tree. Such a minor can easily be improved so that every node is red, by using the meeting nodes. A layer as in the second item is one in which every two nodes meet in a node that is not red; in particular red nodes can only have at most one child. □

### D. Tree decompositions

In this section, we introduce notation for a generalisation of contexts; the idea is that contexts correspond to unary graph terms, and the generalisation corresponds to graph terms of with any number of arguments.

In the main body of the paper, we explained how to each node $X$ in a tree decomposition, we can associate a corresponding induced subgraph. We will also be interested in a generalisation of this notion, where the result is not a graph, but some graph term of type

$$k_1 \times \dots \times k_n \to k.$$

To get such a graph term, we need to specify a node $X$ of rank $k$, which will correspond to the output of the term, and an antichain of nodes $X_1, \dots, X_n$, which have ranks $k_1, \dots, k_n$ respectively, which is contained in $X$. Such a specification is called a *multi-context*, and is denoted by

$$X_1, \dots, X_n \subset X,$$

with the type being defined as above. The arity of a multicontext is the number $n$ of nodes (which corresponds to the number of arguments in the corresponding graph term). Multicontexts of arity zero are the same as nodes,

multicontexts of arity one are the same as contexts. Apart from these, we will be mainly interested in multicontexts of arity two, which correspond to binary graph terms.

To each multicontext we associate a graph term, in the natural way, which is called its *induced graph term*. If we apply the corresponding operation to the subgraphs induced by the nodes $X_1, \dots, X_n$, then we get the subgraph induced by the node $X$.

## APPENDIX TO SECTION III

### E. Composing linearisations

The following lemma shows that linearisations of bounded width can be composed with splits. In the lemma, we use two kinds of sub-decompositions in the presence of a split. The first kind is the local sub-decompositions, which were described after Definition II.11. These describe the relationship between a node and its children, and do not depend on the split. The second kind, which does depend on the split, will be called the *layer sub-decompositions*, these are the sub-decompositions that are induced by layers of the split (recall that each layer is a tree minor, and so it can be used to define a sub-decomposition).

**Lemma A.8.** Let $\mathcal{T}$ be a class of tree decompositions, with each one having an associated split so that:

1) the heights of the splits are bounded;

2) the local sub-decompositions have linearisations of bounded width;

3) the layer sub-decompositions of the splits have linearisations of bounded width.

Then $\mathcal{T}$ also has linearisations of bounded width.

**Proof.** Fix a class $\mathcal{T}$ as in the assumption of the lemma. For every tree decomposition from this class, when talking about the split, we mean the associated split from the assumption of the lemma. Define an *internal node* in a tree to be a node that is neither the root nor a leaf. The proof is by induction on the number of levels assigned by the split to internal nodes.

**Zero levels:** An edge case is when there are no internal nodes, which means that every node is either the root or a leaf. This means that the tree decompositions are the same as the local sub-decompositions of the root, and we can use assumption 2.

**Only one level:** Another important special case, which will do all the work in the induction step, is when all internal nodes use the same level.

Suppose first that the root also uses this level. This means that all the non-leaf nodes in the tree decomposition, including the root, are in the same layer. We call this layer the *outer layer*. The remaining layers are trivial, namely singletons of leaves. Define the *outer linearisation* to be the linearisation of the outer layer, from assumption 3. Consider a part $P$ of the outer linearisation, i.e. an equivalence class of its linear preorder. All vertices from this part are introduced in the same node $X$ with respect to the outer layer. This means that, with respect to the original tree decomposition, they
are introduced in either $X$ or its children that are leaves. Define the inner linearisation for the part $P$ to be the result of taking the order from assumption 2 for the local sub-decomposition describing node $X$ and its children (in the original tree decomposition), and restricting this order to the vertices from the part. Define the combined linearisation to be the lexicographic order of the outer linearisation and the inner linearisation, i.e. we first list all the parts of the outer linearisation according to their order, and inside each part we use the corresponding inner linearisation.

We now show that the combined linearisations satisfy the conclusion of the lemma, i.e. they are indeed linearisations, and they have bounded width. If two vertices are in the same part of the combined linearisation, then they are in the same part of both the outer and the corresponding inner linearisation, and so they are introduced in the same node of the original tree decomposition. It remains to show that the combined linearisation have bounded rank. This is proved in the following claim.

**Claim A.9.** Consider a graph, together with the following linear preorders:

1) an outer preorder;

2) for each part of the outer preorder, an inner preorder.

Then the width of the corresponding combined preorder is at most:

$$2^{\text{width of inner preorder}} + 3 \cdot (\text{width of outer preorder})$$

*Proof of the claim.* Recall the comments in Footnote 3 about the alternative notions of rank. In this proof, it will be more convenient to work with the matrix rank, in the two element field. For two subsets $U$ and $W$ of vertices in a graph, which need not be a partition, we can consider a matrix where the rows are vertices from $U$, the columns are vertices from $W$, and an entry is one or zero, depending on whether there is an edge or not. We can compute two quantities for this matrix

$$\underbrace{\mathbb{F}_2\text{rank}(U, V)}_{\text{number of linearly independent rows}} \quad \text{and} \quad \underbrace{\#\text{rank}(U, V)}_{\text{number of distinct rows}}.$$

We use the latter quantity in this paper for defining ranks of subsets of vertices, but the former quantity will be more convenient in this proof, because of the symmetry of rows and columns. The two quantities are functionally related:

$$\mathbb{F}_2\text{rank}(U, V) \le \#\text{rank}(U, V) \le 2^{\mathbb{F}_2\text{rank}(U, V)}.$$

We will prove a bound on $\mathbb{F}_2\text{rank}$, which will imply an exponentially worse bound on $\#\text{rank}$, as used in the statement of the claim, thanks to the right inequality above.

Consider a prefix of the combined linearisation. Such a prefix can be split into several areas with respect to how it cuts the outer and inner linearisations, as explained in

Figure 1, where the prefix is in red. Because $\mathbb{F}_2\text{rank}$ is subadditive on both arguments, it follows that

$$\begin{align*}
\mathbb{F}_2\text{rank}(\text{prefix}, \text{suffix}) &\le \\
\mathbb{F}_2\text{rank}(\text{outer suffix}, \text{outer prefix}) &+ \\
\mathbb{F}_2\text{rank}(\text{outer suffix}, \text{inner prefix}) &+ \\
\mathbb{F}_2\text{rank}(\text{inner suffix}, \text{outer prefix}) &+ \\
\mathbb{F}_2\text{rank}(\text{inner suffix}, \text{inner prefix}) &
\end{align*}$$

In the first three cases, the two sets can be separated by some prefix of the outer linearisation, and therefore the corresponding rank is bounded by the width of the outer linearisations. In the last case, we use the same argument, but for the inner linearisations. This leads to the claimed bound. □

So far, we have treated the case when the root node is in the same layer as the other nodes. Consider now the case when the root is in a different layer. We use the first case to get a linearisation for each child subtree of the root. Then, we combine these layers using the same technique as previously, except that now the outer linearisation corresponds to the local sub-decomposition at the root, and the inner ones correspond to the layers that are rooted at the children of the root.

*Induction step:* Define the maximal level of a tree decomposition to be the maximal level (used by the split) among those that are used for internal nodes. Consider a tree decomposition $T \in \mathcal{T}$. Among the nodes of this tree decomposition, keep only the root, the leaves, and those among the internal nodes that have maximal rank. Call this the new tree decomposition, and let $T$ be the original tree decomposition.

In the new tree decomposition, all internal nodes have the same level (namely the maximal level), and so we can apply the induction basis to the new tree decomposition. In order to apply the induction basis, we need to ensure the assumptions of the lemma, namely that the local and layer tree decompositions are linear:

1) For the layer sub-decompositions, we simply use assumption 3 for the original tree decomposition;

2) We now prove that the local sub-decompositions of the new tree decomposition are linear. For a node $X$ in the original tree decomposition $T$, define its factor to be the following set of nodes:

$$Y \text{ is a (not necessarily proper) descendant} \\ \{Y \mid \text{of } X \text{ in } T \text{ and all nodes strictly between } X \text{ and } Y \text{ have non-maximal level}\}.$$

The idea is that we start in $X$, and we keep on going down in the tree until we reach a leaf or a node with maximal level; the node we reach this way is also in the factor. By definition, all nodes in the factor that are not the root or its leaves have non-maximal level. Therefore, we can apply the induction assumption to conclude that the sub-decompositions induced by factors
<figure><img src="image_23.png" /><figcaption>Fig. 1. Inner and outer suffixes and prefixes.</figcaption></figure>

are linear. Now we observe that if we take a node $X$ of the new tree decomposition, then the factor of $X$ in the original tree decomposition describes the part between $X$ and its children in the new tree decomposition. Therefore, the sibling sub-decompositions of the new tree decompositions are linear.

Applying the induction basis we then get that the new decomposition is linear. We then combine the obtained linearisation of the new decomposition with the linear decompositions of each factors (obtained by induction, as above) by using Claim A.9 to conclude. □

## APPENDIX TO SECTION IV

This part of the appendix contains additional material about uniform tree decompositions.

We begin with the proof of Lemma IV.2, which says that all recolourings have the same kernel. This simple observation will be the foundation for the notion of supercolours (equivalence classes of the kernel), which is heavily used in the rest of the paper.

*Proof of Lemma IV.2.* We use Lemma A.5 about ideals. Consider two colours $a$ and $b$, and the following property of recolourings: “$a$ and $b$ are mapped to the same colour”. This is an ideal: if $f$ satisfies this property, then the same is true for $e \circ f$. Since the function that assigns a context to its recolouring is forward invariant, we can use Lemma A.5 to conclude that either all or none of the recolourings satisfy this property. This means that all the recolourings have the same kernel. □

As we mentioned in the main body of the paper, we cannot assume that all recolourings are the same, but we must work with weaker properties, such as the one from the above lemma. However, it is useful to observe that we can always extract large sub-decompositions where the recolourings are indeed the same, as shown in the following lemma.

**Lemma A.10.** Consider a class $\mathcal{T}$ of tree decompositions where the 0-theories are forward invariant. If $\mathcal{T}$ has unbounded Strahler number, then there is some recolouring $e$ such that

$$ \mathcal{T}_e = \{T \mid T \text{ is a sub-decomposition of } \mathcal{T} \text{ where all contexts have recolouring } e\}. $$

also has unbounded Strahler number.

*Proof.* Define the parent recolouring of a node in a tree decomposition to be the recolouring of the context which consists of that node and its parent. For a recolouring $e$, and a tree decomposition $T$ from the class, define its $e$-minor to be the tree minor consisting of nodes whose parent recolouring is $e$. Using the same argument as in Example 8, one can use Lemma A.7 to conclude that if a tree decomposition has large Strahler number, then there is some recolouring $e$ such that the corresponding $e$-minor also has large Strahler number. Therefore, there must be some recolouring $e$ such that the $e$-minors of $\mathcal{T}$ have unbounded Strahler number. Finally, we observe that thanks to forward invariance, if we take an $e$-minor, and we shift each node to its parent, then the resulting minor has recolouring $e$ on every context. □

The following lemma shows that the superflips are compatible with forward invariance of theories.

**Lemma A.11.** If a tree decomposition has forward invariant $q$-theories (and therefore it also has supercolours), then the same is true after applying any superflip.

*Proof.* Since the supercolours to not change throughout the tree decomposition, applying a superflip to the entire tree decomposition is the same thing as applying the same superflip to each context independently. Recall that a semigroup automorphism is a permutation of the semigroup that is consistent with the semigroup operation. If we take an additive labelling that is forward invariant, and we postcompose it with a semigroup automorphism, then the result is still forward invariant. Therefore, to complete the proof of the lemma, it is enough to show that superflips are a special case of a semigroup automorphism.

**Claim A.12.** Let $k \in \{1, \dots, k\}$, and consider the semigroup of $q$-theories of graph terms of type $k \to k$. Flipping any two colours is an automorphism of this semigroup.

*Proof.* This is because a flip of two colours is an example of a quantifier-free interpretation, see [5, Section III.B], and such interpretations are compatible with $q$-theories. □

Since a superflip can be decomposed into a sequence of flips of individual colours, we get the desired result. □
**Reduction to uniform classes:** We now prove the main technical result of Section IV, Lemma IV.7, which shows that the Dichotomy Lemma can be reduced to the case of uniform classes.

**Proof of Lemma IV.7.** Suppose that the Dichotomy Lemma holds for uniform classes. We will now prove it for all classes. The proof is by induction on the width of the tree decompositions in the class. Suppose that we have proved the Dichotomy Lemma for classes of tree decompositions that have width strictly smaller than $k$, and we want to prove it for a class $\mathcal{T}$ that has width at most $k$. (For this induction, the induction basis is treated the same way as the induction step. In the following paragraph, there will be another nested induction, where the induction basis is treated differently from the induction step.)

By Theorem A.4, to each tree decomposition in $\mathcal{T}$ we can associate a split so that the splits have bounded height, and in the layer sub-decompositions, the $q$-theories of contexts are forward invariant. By choosing an arbitrary order on $q$-theories and labelling each node with its $q$-theory, we can further refine the split so that on each layer, all nodes have the same $q$-theory. This ensures assumptions 1 and 2 of uniformity, but not assumption 3 about colour connectedness. For each level $\ell$ of the splits (i.e. an element of the linearly ordered set that is used to label nodes), define $\mathcal{T}_\ell$ to be the class of sub-decompositions that arise from layers at level $\ell$. By induction on $\ell$, we will show that the conclusions of the Dichotomy Lemma hold for $\mathcal{T}_\ell$.

Suppose that we have proved this for strictly smaller levels, and we want to prove it for $\ell$. By induction we may assume that all the classes for strictly smaller levels have linearisations of bounded width, otherwise we already know that a regular branching class is covered. Therefore, the local sub-decompositions of $\mathcal{T}_\ell$ have linearisations of bounded width, thanks to Lemma A.8. By definition, all tree decompositions in $\mathcal{T}_\ell$ satisfy assumptions 1 and 2 of uniformity. For the tree decompositions in $\mathcal{T}_\ell$ that are not colour connected, we can split them into connected components, and apply the outer induction hypothesis on smaller width to get the conclusion of the Dichotomy Lemma. We are left with the subclass $S_\ell \subseteq \mathcal{T}_\ell$ of tree decompositions that are colour connected, and therefore uniform. Since there are finitely many possibilities for the theories in item 1 and the subsemigroups in item 2, it follows that $S_\ell$ partitions into finitely many uniform classes. We can now apply the special case of the Dichotomy Lemma to these uniform classes. □

**Compatibility with superflips:** We finish this part of the appendix by proving Lemma IV.8, which says that superflips are compatible with both the assumptions and the conclusions in the Dichotomy Lemma.

**Proof of Lemma IV.8.** We begin with uniformity. The main condition here is forward invariance of $q$-theories, which was already proved in Lemma A.11 to be compatible with superflips. The proof for all nodes having the same $q$-theory

is done in the same way. For colour connectedness, there is nothing to do, since the condition itself has superflips built into its definition.

Let us now show that having bounded linear cliquewidth is compatible with superflips. In fact, it is compatible with any kind of flips: doing a flip of one subset of vertices against another can only increase the rank of a subset by a constant amount. Therefore, we can use the same linear decompositions, and the linear cliquewidth will continue to be bounded.

Finally, let us show that transducing all trees is compatible with superflips. Here again, the condition is compatible with any kind of flips, since any constant number of flips can be reversed by an MSO transduction. □

## THE DICHOTOMY LEMMA WHEN ALL EDGES ARE LOCAL

In this part of the appendix, we prove Lemma V.2, which says that the Dichotomy Lemma holds for uniform classes of tree decompositions where all edges are local. In this case, when trees will be transduced, they will be transduced in a simple way: via vertex deletions and edge contractions. This is a somewhat stronger conclusion than the one in the Dichotomy Lemma; however in the presence of non-local edges, the transductions will need to be a bit more involved.

**Outer paths:** In the proof, we will make a further case split, depending on a certain connectivity property of contexts. For a context $X \subset Y$, we call the smaller node $X$ an *argument*. The idea is that this node is turned into an argument in the corresponding unary graph operation. We will be interested in paths that avoid edges contained in the argument.

**Definition A.13 (Outer path).** An outer path in a context $X \subset Y$ is a path where all vertices are from $Y$, and which does not use any edge contained in the argument $X$.

Observe that vertices from the argument $X$ are allowed in an outer path, however every edge must use at least one vertex that is not in the argument. Here is a picture:

<figure><img src="image_24.png" /></figure>

We will be interested in how colours of the argument in a context can be connected using outer paths. For a context $X \subset Y$, and a colour $a$, we define *port* $a$ of the context to be the set of vertices $X.a$. (In other words, this is the contextual class of $X$ that is coloured with $a$ in the tree decomposition.) Since the port is a contextual class, one can think about it as a single vertex with respect to the complement of $X$, in particular with respect to all vertices that are introduced in the context. Our proof of the Dichotomy Lemma, under the local edge property, is based on the analysis of connections
between ports via outer paths, as described in the following definition.

**Definition A.14** (Outer components). Consider a context $X \subset Y$ in a uniform tree decomposition. We say that two colours $a$ and $b$ are in the same outer component of the context if there is an outer path from $X.a$ to $X.b$.

**Lemma A.15.** Being in the same outer component is a transitive relation.

*Proof.* Suppose that we have an outer path in a context $X \subset Y$ from port $a$ to port $b$, and another outer path from port $b$ to port $c$. The only difficulty is that a port is not a single vertex, but an entire contextual class. Therefore, the two intermediate vertices in port $X.b$, i.e. the target of the first path and the source of the second path, need not be equal. We show that the first path can be modified so that such an equality does hold.

Consider the last edge $vw$ used in the first path, which connects some vertex $v$ to the target vertex $w \in X.b$ of the first path. Since edges in outer paths cannot be contained in the argument $X$, and $w$ belongs to the argument, it follows that $v$ does not belong to the argument. Therefore, the connections between $v$ and vertices in the argument $X$ depend only on the colours of the latter vertices, and so $v$ has an edge to every vertex in $X.b$. Therefore, we can modify the first path so that its target vertex is equal to the source of the second path. $\square$

Clearly the relation in the above lemma is also symmetric. It is not, however, an equivalence relation, since it might not be reflexive, i.e. some colours inside the argument might not have any edges to the exterior. In fact, it will certainly not be reflexive, as will be explained in Lemma A.16 below. (The statement below is not essential to the current proof, but it will be used later, and it gives a good intuition about outer components, and more generally about the structure of uniform tree decompositions with local edges.)

**Lemma A.16.** Consider a uniform tree decomposition with the local edge property. Then for every node $X$ and fixpoint colour $a$, there is no edge from $X.a$ to any vertex outside $X$.

*Proof.* The argument in this proof was already used in Lemma IV.2, and will also appear several times later in this paper. We show that some property is an ideal and definable in MSO, with the quantifier depth being smaller than the fixed quantifier depth $q = 9$ in the definition of uniform tree decompositions. This will allow us to use Lemma A.5 to show that the property holds everywhere or nowhere.

We have defined the notion of ports for contexts $X \subset Y$. The notion can also be extended to unary graph terms. We define port $a$ in a unary graph term to be the vertex in the argument whose number is $a$, with respect to the order on vertices in the argument that is part of the definition of graph terms. The idea is that if we apply a unary graph term $E$ to some graph $G$, then all vertices with colour $a$ in $G$ will be substituted into port $a$ of $E$.

For a colour $a$ used in the tree decomposition, and a context $X \subset Y$, consider the following property of the unary graph terms corresponding to the context:

(*) there is an edge from port $a$ to some vertex that is not a port.

We will prove that for every context $X \subset Y$ and every fixpoint colour $a$, the property (*) is not satisfied by the corresponding graph term. This will complete the proof of the claim, by considering contexts where the bigger node $Y$ is the root.

We first show that if property (*) holds for some $a$ and some context, then it holds for the same $a$ in all contexts. Property (*) is clearly expressible in MSO using low quantifier depth (in fact, a first-order formula with one quantifier). If a unary graph term $E$ satisfies this property, and $F$ is any other unary graph term, then also $F \cdot E$ satisfies this property. Therefore, this property is an ideal in the semigroup of unary graph terms. We can thus apply Lemma A.5 to conclude that for every colour $a$, the property (*) is invariant in a uniform tree decompositions, i.e. it is satisfied either by all or none of the (unary graph terms corresponding to the) contexts in the tree decomposition.

We now show that if property (*) holds for some fixpoint colour (we no longer need to specify the context, since we have shown that the property is independent of the context), then it holds for all colours in the same supercolour. Suppose that some fixpoint colour $a$ satisfies (*). We will show that (*) holds for every other colour $b$ in the same supercolour. (Although for the purposes of this claim, we only care about the case when $b$ is a fixpoint.) By definition of fixpoint colours, there is some recolouring that is used in the tree decomposition, which maps $b$ to $a$. Let $E$ be the unary graph term corresponding to this tree decomposition. By assumption on $a$, $E$ satisfies (*) for $a$. This implies that $E \cdot E$ satisfies (*) for $b$, because colour $b$ is first recoloured to $a$ in the right copy of $E$, and then it has an edge to some vertex in the left copy. Since the theory of $E$ is idempotent, it follows that $E$ satisfies (*) for $b$.

Let us now complete the proof of the claim. Consider two consecutive contexts $X \subset Y \subset Z$ in a tree decomposition from our class. (If we cannot find such contexts, this means that every tree decomposition consists only of the root and leaves. This means that the local sub-decomposition of the root is the same as the tree decomposition itself, and thus there is nothing to prove in the Dichotomy Lemma.) Toward a contradiction, suppose that (*) would be satisfied by some fixpoint colour. Then it would be satisfied by some fixpoint colour, call it $a$, that is in the image of the recolouring of the context $X \subset Y$. This would mean that there is an edge from $X.a$ to some vertex introduced in the context $Y \subset Z$, thus violating the assumption on local edges. $\square$

Let us return to the outer component relation from Definition A.14. We have argued that it is symmetric and transitive, but not necessarily reflexive. Therefore, the relation groups the colours into parts, which we call *outer components*, that
are disjoint but do not cover all colours. (As explained in Lemma A.16, fixpoint colours will not belong to any outer component.) The following lemma shows that the notion of outer components is invariant in a uniform class, i.e. all contexts in all tree decompositions have the same notion of outer component.

**Lemma A.17.** In a uniform class of tree decompositions, outer components are invariant.

*Proof.* The equivalence relation in the definition of outer components can be read from the theory of the context. Furthermore, the existence of an outer path from colour *a* to colour *b* is an ideal. Therefore, the outer components are invariant by Lemma A.5. □

Thanks to the above, it makes sense to talk about outer components in a uniform class, without referring to a particular context or tree decomposition.

*Recurrent outer components:* We will be mainly interested in certain outer components, which we will called recurrent. The idea is that a recurrent outer component can traverse a context $X \subset Y$, i.e. it can be used to connect vertices from $X$ with vertices outside $Y$. The formal definition of this concept needs some preparatory material, and will be presented later in this section. For a node $X$ in a tree decomposition and a set of colours $A$, we write $X.A$ for the union of $X.a$ where $a$ ranges over $A$.

**Definition A.18 (Profile).** Define the profile of a context $X \subset Y$ in a uniform tree decomposition to be the following binary relation on outer components

$$ \{(A, B) \mid A \text{ and } B \text{ are outer components such that the context admits an outer path from } Y.A \text{ to } X.B \} $$

Observe that the swapped order of arguments: colours $A$ are used in the bigger node $Y$, and colours $B$ are used in its descendant $X$. The following lemma will be the foundation for the notion of recurrent outer components – these will be defined (see Definition A.22) – to be those that satisfy the second condition in the lemma.

**Lemma A.19.** Let $X \subset Y$ be a context in a uniform tree decomposition. Then

1) its profile is a partial function; and

2) this partial function is idempotent;

3) if an outer component $A$ is such that $(A, A)$ belongs to the profile of some context in the tree decomposition, then it belongs to the profiles of all contexts.

*Proof.* We begin with the first item, about partial functions.

**Claim A.20.** For every context and every outer component $A$, there is at most one outer component $B$ such that $(A, B)$ belongs to the profile of the context.

*Proof.* Toward a contradiction, suppose that for some context $X \subset Y$, the profile contains $(A, B_1)$ and $(A, B_2)$ for two different outer components $B_1 \neq B_2$. Let $E$ be the unary graph term that corresponds to this context. The following

picture shows that if we compose $E$ with itself, then in the resulting unary graph term $E \cdot E$, we get an outer path from some port in $B_1$ to some port in $B_2$:

<figure><img src="image_25.png" /></figure>

Since the existence of such a path can be read from the mso theory, and the theory of $E$ is idempotent, it follows that such a path would exist also in the original unary graph term $E$, contradicting the assumption that $B_1$ and $B_2$ are two different outer components. □

Inspired by the above claim, instead of saying that $(A, B)$ belongs to the profile, we say that $A \mapsto B$ belongs to the profile, to underline the fact that the profile is a partial function from the first argument to the second one. The following claim shows that composition of such partial functions is consistent with composition of graph terms. (To avoid confusion, let us recall how we compose unary graph terms: in the composition $G \cdot H$, the argument of $G$ is replaced by $H$.) The following claim shows that mapping a unary graph term to its profile is a homomorphism, from unary graph terms to partial functions on outer components.

**Claim A.21.** Consider two unary graph terms $G$ and $H$ which arise from contexts in the class of tree decompositions. If $A \mapsto B$ belongs to the profile of $G$ and $B \mapsto C$ belongs to the profile of $H$, then $A \mapsto C$ belongs to the profile of their composition $G \circ H$.

*Proof.* Essentially the same argument as in Claim A.20, see the following picture:
<figure><img src="image_26.png" /></figure>

<figure><img src="image_27.png" /></figure>

Since profiles can be read from MSO theories, and MSO theories are idempotent, it follows that the profiles are idempotent, thus proving the second item of the lemma.

Consider now the last item of the lemma, which says that if $(A, A)$ belongs to one profile, then it belongs to all profiles. As we have proved above, the profiles are idempotent partial functions. This means that $(A, A)$ belongs to a profile if and only if $A$ belongs to the image of the corresponding partial function. Therefore, we need to show that if $A$ belongs to the image of some profile (when viewed as a partial function), then it belongs to the images of all profiles. This is a simple corollary of forward invariance, since the image of the profile of $E \cdot F$ is contained in the image of $F$, and also equal to the image of the profile of $E$. Therefore all profiles have the same image<fnref n="5" />.

<figure><img src="image_28.png" /></figure>

The outer components which satisfy the conditions from the above lemma will be of particular interest in our proof, so we give them a name.

**Definition A.22** (Recurrent outer components). An outer component in a uniform tree decomposition is called recurrent if it belongs to the image of some (equivalently, every) profile in the tree decomposition.

If we take a uniform class of tree decompositions, then all tree decompositions in this class will have the same recurrent outer components, and therefore it is meaningful to speak about the recurrent outer components of a uniform class.

Vertices in recurrent outer components admit good connectivity properties, that we describe in the two following lemmas.

**Lemma A.23.** Consider a recurrent outer component $A$, and a node which is not the root. All vertices whose colour with respect to that node belong to $A$ are connected in the underlying graph.

*Proof.* Take a node $X$ which is not the root and let $Y$ be its parent. Since $A$ is an outer component, all vertices in $X.A$ are connected. □

<figure><img src="image_29.png" /></figure>

**Lemma A.24.** Consider a recurrent outer component $A$. Two vertices that belong respectively to $X_1.A$ and $X_2.A$ where $X_1$ and $X_2$ are (not necessarily proper) descendants of the same child of the root, are connected in the underlying graph.

*Proof.* This follows from the previous claim, and the fact that since $A$ is recurrent, for any context $X \subset Y$ where $Y$ is the parent of $X$, vertices in $X.A$ are connected to some vertex in $Y.A$. □

<figure><img src="image_30.png" /></figure>

To prove the Dichotomy Lemma under the local edge assumption, we will do a case analysis depending on the number of recurrent outer components, which can be zero, one, or at least two. These cases are treated in Sections F-H below. In the case of one recurrent outer component, we will prove that trees are transduced (in a very simple way, namely using vertex deletions and contractions), while in the remaining cases (zero or at least two), we will have linearisations of bounded width.

### F. Zero recurrent outer components

In this section, we show that the Dichotomy Lemma holds for every uniform class which has only local edges and zero recurrent outer components. In this case, the conclusion will be that there are linearisations of bounded width. This will be proved by showing that all connected components are covered by the local sub-decompositions, as explained in the following lemma.

**Lemma A.25.** Consider a uniform tree decomposition where all edges are local, and which has zero recurrent outer components. Then for every connected component of the underlying graph, there is a node such that all vertices of the connected component are introduced in that node and its children.

*Proof.* We will show that for every context $X \subset Y$, there cannot be a path in the underlying graph that traverses this context, i.e. it connects some vertex from $X$ with some vertex in the complement of $Y$. Toward a contradiction, suppose that there is such a path, and choose the path so that it has minimal length. By minimality, the source of the path is in $X$, the target is in the complement of $Y$, and all of the remaining vertices are in $Y \cup X$, i.e. they are introduced in the context. Let $a$ be the colour, from the point of view of $Y$, of the penultimate vertex in the path. Since the penultimate vertex has an edge (namely the last edge in the path) to some vertex outside $Y$, it follows that $a$ belongs to some outer component (from the perspective of the context $Y \subset \text{root.}$) Call this component $A$. Consider now the first vertex in the path, and let $b$ be its colour, from the perspective of the node $X$. For similar reasons, $b$ also belongs to some outer component, call it $B$. Finally, the inner part of the path witnesses a connection from $Y.A$ to $X.B$, and thus $B$ belongs to the image of the profile of the context $X \subset Y$,

<footnote n="5">⁵This is a somewhat dual argument to the one in Lemma IV.2. In this lemma, the functions are top-down, i.e. they are directed from $Y$ to $X$. In Lemma IV.2, the functions are bottom-up, i.e. they are directed from $X$ to $Y$. In the top-down case, the images are invariant, while in the bottom-up case, the kernels are invariant.</footnote>
which means that the profile of $X \subset Y$ has at least one
recurrent outer component. $\square$

Using the above lemma, let us show that Dichotomy Lemma, under the assumption that all edges are local, and there are zero recurrent components. The above lemma shows that each connected component is encompassed by some local sub-decomposition. Since such sub-decompositions have linearisations of bounded width in the assumptions of the Dichotomy Lemma, it follows that for every connected component, there is a linearisation of bounded width. By listing these linearisations in some arbitrary order, ranging over the connected components, we get a linearisation of bounded width for the entire graph, thus proving the Dichotomy Lemma for the case of zero recurrent outer components.

### G. One recurrent outer component

We now prove the Dichotomy Lemma in the case where all edges are local, and there is one recurrent outer component. We also assume unbounded Strahler number, thanks to the following lemma.

**Lemma A.26.** The Dichotomy Lemma holds for classes of tree decompositions that have bounded Strahler number.

*Proof.* If a class of tree decompositions has bounded Strahler number, then to each tree decomposition we can associate a split, so that the splits have bounded height, and the layers are linear, i.e. on every layer all nodes are on a single branch. This is done by applying Lemma A.7, for a trivial Strahler constraint that consist of all pairs of disjoint nodes. For linear tree decompositions, we trivially have linearisations of bounded width. Therefore, we can apply Lemma A.8 to get linearisations of bounded width. $\square$

In Lemma A.28, we will show that if the Strahler number is unbounded, there are only local edges, and one recurrent outer component, then all trees are transduced. As mentioned before, the transduction will be very special. We will only use vertex deletions and contractions. Let us begin by recalling the notion of contraction.

*Contractions:* By contraction, we mean the following operation: take a subset $X$ of vertices, whose induced subgraph is connected, and replace the subset by a single vertex, which is adjacent to the vertices that were adjacent to at least one vertex in $X$ in the original graph. Contracting an entire connected subset can be replaced by a sequence of edge contractions, but it will be useful to contract entire subsets in a single step.

**Example 9.** [Separating vertices] A separating vertex in a connected graph is a vertex whose removal makes the graph disconnected. Consider a connected graph, and let $\mathcal{X}$ be the connected components after removing the separating vertices. (These are the 2-connected components of the graph.) The sets in $\mathcal{X}$ are connected and pairwise independent. Therefore, we can apply contraction to them, as shown in the above picture:

before contraction

<figure><img src="image_31.png" /></figure>

after contraction

<figure><img src="image_32.png" /></figure>

The result will be a tree (more precisely, the child graph of some tree). This is because the separating vertices in a graph are equipped with a natural tree structure. $\square$

This corresponds to the following notion of contractions.

**Definition A.27 (Independent contraction).** An independent contraction of a graph is any graph that can be obtained as follows. Choose a family $\mathcal{X}$ of pairwise independent connected subsets (i.e. there are no edges between two different subsets), and contract each subset from $\mathcal{X}$.

Note that independent contractions are MSO transductions. The following lemma proves a more precise version of the Dichotomy Lemma in the case of one recurrent outer component.

**Lemma A.28.** Let $\mathcal{T}$ be a uniform class of tree decompositions, which has:

1) only local edges; and

2) one recurrent outer component; and

3) unbounded Strahler number.

Then there is $k \in \{0, 1, 2, \dots\}$ such that every acyclic graph can be obtained from some graph (underlying a tree decomposition) in $\mathcal{T}$ by applying some a sequence of vertex deletions and $\le k$ independent contractions.

*Proof of Lemma A.28.* Let $A$ be the unique outer component that is recurrent, from the second assumption in the lemma. Recall from Lemmas A.23 and A.24 that vertices with colour from $A$ are well-connected in the underlying graph. We will then study separators in the graph. We start with the following observation which states that $X.A$ separates $X$ and its complement.

**Claim A.29.** Consider a node $X$ in a tree decomposition from the class. Then edges from $X$ to its complement have an endpoint in $X.A$.

*Proof.* Consider an edge from $X$ to its complement and let $Y$ denote the whole graph. Let $B$ and $C$ denote the end components such that the edge has its endpoints in $Y.B$ and $X.C$, so that $B \mapsto C$ belongs to the profile. Then $C$ is in the image of the profile, so $C = A$. $\square$
We now identify connected separators which we will call
centers. For a context $X \subset Y$ in a tree decomposition, define
the vertices *introduced* by this context to be the vertices from
$Y \diagdown X$. The proof below relies on idempotence of the theory
of contexts in a uniform class of tree decompositions.

**Claim A.30.** Let $X \subset Y$ be a context in a tree decomposition from $\mathcal{T}$. There is a subset of the vertices introduced in this context, which we call the center, such that:

1) the subgraph induced by the center is connected;

2) every path from $X$ to a vertex outside $Y$ must use a vertex from the center.

*Proof.* Let $G$ be the unary graph term that is induced by the context. Note that the property in the statement of the claim can be expressed in MSO with quantifier rank at most 2: this is because being connected to a vertex outside of $Y$ is a property of the colours within $Y$; we say that a colour $c$ communicates with the exterior if there is an edge (equivalently, all edges), from $Y.c$ to the complement of $Y$. In particular, this implies that $c \in A$ by Claim A.29. So condition (2) can be expressed by saying that the center intersects all paths from the argument to vertices whose colours communicate with the exterior.

We now show that the property from the statement of the
claim holds in $G \circ G$, i.e. the result of composing $G$ with
itself. Since the quantifier depth 2 theory is idempotent for
$G$, it follows that also $G$ must have the property from the
statement of the claim, i.e. existence of a center.

In the composed operator $G \circ G$, let $W$ denote the set of
vertices with colour $A$ which are introduced in the deeper
copy (but excluding vertices from the argument). By the
assumption that $A$ is a single outer component, we know
that $W$ is connected inside $G \circ G$, using only outer paths
avoiding the argument. For each pair of vertices of $W$, fix
a path inside $G \circ G$ avoiding the argument and connecting
the two vertices, and define the candidate center to be the
union of all these paths. By Claim A.29 any path from the
argument in $G \circ G$ to a colour which communicates with the
exterior visits a vertex from $W$, and therefore this is indeed
a center.
□

We are now ready to prove that the class covers all trees.
In the proof, say that a tree minor is *3-separated* if nodes that
belong to the minor are at distance $\ge 3$ in the child tree. The
following straightforward claim shows that separated minors
can be extracted without too much decrease in the Strahler
number.

**Claim A.31.** If a class of trees has unbounded Strahler number, then the same is true for the class of its separated minors which exclude the root.

*Proof.* First take a tree minor that is a large binary tree, and
then restrict to a subset of its nodes by proceeding top-down,
taking a child of the root then skipping every level that is not
a multiple of 3 to make it 3-separated. This will divide the

Strahler number by 3 and remove 1, but keep it unbounded.

□

Take a 3-separated minor $S$ of some tree decomposition $T \in \mathcal{T}$ which excludes the root; in particular all nodes in $S$ are $T$-descendants of the same child of the root. For each node $X$ that appears in $S$, apply Claim A.30 to the context $X \subset Y$ consisting of $X$ and its parent $Y$ in the original tree decomposition $T$, yielding some center. We will call this the parent center of $X$. The following claim shows that parent centers are independent, i.e. there are no edges between them.

**Claim A.32.** For every two different nodes of $S$, their parent centers are independent.

*Proof.* In a separated minor, any two nodes of the minor are not nearby in the original tree. The same holds for parents of nodes in the minor. Therefore, the claim follows from the assumption that all edges are local.
□

Consider a 3-separated minor $S$ of a tree decomposition
from $\mathcal{T}$, such that the underlying tree is a binary tree.
Define the central contraction of $S$ to be the graph that is
obtained from the underlying graph in $S$ by contracting the
parent centers of all nodes in $S$. Because parent centers are
connected and pairwise independent, this is an independent
contraction. By Claim A.30, for any node $X$ of $S$, all paths
from $X$ to vertices introduced in $S$-nodes that are not $S$-
descendents of $X$, use a vertex from the parent center of
$X$. Moreover thanks to Lemma A.24, all the centers are
connected.

Therefore for each pair of nodes $X \subset Y$ in $S$ such that $X$ is a child of $Y$, there is a path inside $Y \diagdown X$ whose endpoints are respectively connected to the parent centers of $X$ and $Y$. For each such pair $X \subset Y$, we fix a path as above. Note that by Claim A.30, there cannot be any edges between two such paths. We conclude by taking the restriction to the centers and the paths, and contracting all the paths, which is an independent contraction.
□

H. At least two recurrent outer components

We now prove the Dichotomy Lemma in the case where
there are at least two recurrent outer components.

**Lemma A.33.** Let $\mathcal{T}$ be a uniform class of tree decompositions, which:

1) has the local edge property;

2) there are at least two outer components that are recurrent;

3) the local sub-decompositions have linearisations of bounded width;

Then $\mathcal{T}$ has linearisations of bounded width.

*Proof.* The proof will be based on an extended analysis of connectivity.

The following claim shows that a colour from an outer
component can only be used in the node that introduces a
vertex.
**Claim A.34.** Let $A$ be an outer component, recurrent or not. For every node $X$ of a tree decomposition in $\mathcal{T}$, all vertices from $X.A$ are introduced in $X$.

*Proof.* As shown in Lemma A.16, a consequence of the local edge property is that outer components cannot contain fixpoint colours. Therefore, vertices from $X.A$ cannot be introduced in descendants of $X$, since otherwise they would have a fixpoint colour by the time they reach $X$. $\square$

Recall from 3 in Definition IV.6 that uniform decompositions are colour connected: there exists a connected component of the underlying graph and a node $X_0$ such that all colours are touched by the component in $X_0$. We will see that the case at hands, this has far-reaching implications on connectivity within each node.

**Claim A.35.** There exists a connected graph $C$ over the recurrent components such that for every edge $AB$ in $C$ and for every node $X$ there is a path contained in $X$ between $X.A$ and $X.B$.

*Proof.* We prove that the property above holds for $X_0$, which implies the claim since MSO theories of quantifier rank 2 of all nodes are the same. We define $C$ to be comprised of edges $AB$ such that in the underlying graph, there is a path $P$ connecting $X.A$ and $X.B$ of minimal length (among all paths connecting $X.A$ and $X.B$), which is internally disjoint from all $X.D$, where $D$ is a recurrent component. Since there is a connected component of the underlying graph that touches all colours in $X_0$, the graph $C$ is indeed connected.

There remains to argue that a path $P$ as above is contained in $X$. This is because all edges from a vertex $x \in X$ to the complement of $X$ are such that $x \in X.D$ for some recurrent component $D$. $\square$

For a tree decomposition in $\mathcal{T}$, a *detached connected component* is defined to be a connected component in the underlying graph such that for some node $X$, all vertices of the connected component are introduced in $X$. A *detached vertex* is a vertex whose connected component is detached. We will be mainly interested in non-detached components and vertices, which we call *attached*. The following claim justifies the terminology by proving that these are well-connected to the rest of the graph. We define the *connected components of a node* to be the connected components in the induced subgraph of that node.

**Claim A.36.** For every node $X$, all attached vertices in $X$ have a path in $X$ connecting them to $X.A$ for some recurrent component $A$.

*Proof.* Consider some attached vertex $x$ from $X$, and let $C$ be the connected component of $x$ in the full underlying graph. If $C$ is not contained in $X$, then take a path of minimal length connecting $x$ with the complement of $X$, and observe that the last edge from this path, which is the only one which is not contained in $X$, has an endpoint in $X.A$ for some recurrent component $A$. Otherwise, $C$ is contained in $X$ and

therefore $x$ has a path in $X$ towards a vertex in $Z.A$, where $Z$ is a proper descendent of $X$ and $A$ is a recurrent component. Then the result also follows since:

1) $Z.A$ is connected in $X$ (this is because $A$ is an outer component in the context $Z \subset X$); and

2) there is a path from $X.A$ to $Z.A$ (this is because $A \mapsto A$ belongs to the profile of $Z \subset X$). $\square$

We are now ready to state the key technical result in this section.

**Claim A.37.** Let $A$ and $B$ be different recurrent components, and let $Y$ be a node. Then every path in the induced subgraph of $Y$ from $Y.A$ to $Y.B$ must pass through all descendants of $Y$ in the tree decomposition.

*Proof.* Let $X$ be a descendant of $Y$, and assume for contradiction that there is a path from $Y.A$ to $Y.B$ which avoids $X$. By definition of recurrent components, we also have paths from $X.A$ to $Y.A$ and from $X.B$ to $Y.B$. Let $E$ denote the theory of the context $X \subset Y$. Then by definition of outer components, the dashed paths in the picture below appear in $E \circ E$.

<figure><img src="image_33.png" /></figure>

We conclude by idempotence that in $E$, there is an outer path from $X.A$ to $X.B$, a contradiction. $\square$

For a node $X$, define its *contracted graph* to be the graph obtained by taking the induced subgraph of $X$, removing detached vertices, and contracting each child of $X$ to a single vertex. Using the above claim, we will show that the contracted graph must have a very special shape, namely it is essentially a path that passes through the contracted children in some fixed order, as in the following picture:
<figure><img src="image_34.png" /></figure>

**Claim A.38.** Let A and B be recurrent outer components. Then for every node X, there is an ordering on its child nodes, such that every path from X.A to X.B in the contracted graph of X must pass through the corresponding vertices in the given order.

*Proof.* By Claim A.37, each contracted vertex separates the sets X.A and X.B in the contracted graph of X. The statement then follows from the structure of vertices that separate two sets. □

The analysis from the above claim gives us a slightly surprising corollary.

**Claim A.39.** *There cannot be more than two recurrent outer components.*

*Proof.* Suppose that there is a third recurrent component. Choose a node so that it has at least two children (this must happen at least once in the class). In the corresponding contracted graph, there is no place to put a vertex from the third component. □

For the rest of this proof, fix the only two recurrent outer components, call them A and B. We now give a more refined version of the observations from Claim A.38 about the linear structure. In this more refined version, we care about the colours of vertices in the children of a node.

Consider an attached vertex $x$ that is introduced in a node $X$. Define the *prefix* of $x$ to be:

$$ \{Z \mid Z \text{ is a child of } X \text{ that appears in every path from } X.A \text{ to } x \} $$

We call this set a prefix because it is a downward closed set with respect to the linear order from Claim A.38. We will use the prefixes to impose a linear preorder on the vertices from the node. There will be two kinds of attached vertices participating in this preorder: the vertices from the children of this node, and the vertices introduced in $X$. For the former vertices, we use the order $X_1 < \dots < X_n$ on children from Claim A.38. For the latter vertices, we use the prefixes to get the order. The two orders are put together as follows, with the vertices introduced in $X$ written in red:

$$ \begin{array}{l} \text{prefix } \emptyset < \\ X_1 < \text{prefix } \{X_1\} < \\ X_2 < \text{prefix } \{X_1, X_2\} < \\ \dots < \\ X_n < \text{prefix } \{X_1, \dots, X_n\}. \end{array} $$

The above linear preorder is called the *local order at X*; it orders all vertices in $X$ that are attached.

We now use the local orders to define a linear preorder on all vertices in the tree decomposition. First, we look at the connected components in the entire graph, and order them arbitrarily. Over detached components, the order is not further refined. Inside each attached connected component, we order the vertices as follows: for two vertices $v$ and $w$, we look at the smallest node that contains both of them, and order them using the local order at that node. Call the resulting order the *global order*.

**Claim A.40.** *For every tree decomposition in $\mathcal{T}$, the global order is a linearisation.*

*Proof.* We should show that vertices in the same part are introduced in the same node. If two vertices are in the same part, then they are in the same connected component. If the component is detached then by definition it is included in some node. Assume that the component is attached. Let $X$ be the smallest node that contains both vertices. Since the two vertices are in the same part, it means that they are in the same part with respect to the local order of $X$. They cannot be in the same part that corresponds to a child of $X$, since otherwise $X$ would not be the smallest child containing them. Therefore, they are in a part (coloured red when defining the local order) of the local order that corresponds to vertices introduced in $X$. □

We will now show that the global orders have bounded width. The main observation is in the following claim, which shows that in the global order, edges connect vertices whose parts are at distance at most two in the linear order on parts (the distance is zero when vertices are from the same part, one when they are in consecutive parts, and two when they are from parts that have exactly one part between them).

**Claim A.41.** *For every edge in the underlying graph, the parts of the endpoints are at distance at most two.*

*Proof.* The result is clear for edges within detached components, so we focus on the attached ones. Consider an edge $vw$ such that $v$ and $w$ are attached vertices in different parts, say $v$ is strictly before $w$. We will show that the corresponding parts are at distance one or two (we have excluded zero by assuming that the vertices are in different parts).

Let $X$ be the smallest node that contains both $v$ and $w$, and consider the local order at this node:

$$ \begin{array}{l} \text{prefix } \emptyset < \\ X_1 < \text{prefix } \{X_1\} < \\ X_2 < \text{prefix } \{X_1, X_2\} < \\ \dots < \\ X_n < \text{prefix } \{X_1, \dots, X_n\}. \end{array} $$

We prove the claim by a case analysis, depending on whether the vertices come from black parts (corresponding to chil-
dren) or red parts (corresponding to vertices introduced in the sub-node).

1) It cannot be the case that both $v$ and $w$ are in red parts. This is because thanks to Claim A.37, there are no edges between two different red parts.

2) Suppose now that the earlier vertex $v$ belongs to a black part, and the later vertex $w$ belongs to a red part. Let $X_i$ be the child that contains $v$. Using the edge to the later vertex $w$, we get a path from $v$ to $X.B$, which does not visit node $X_i$ except for the first vertex. This is an outer path from $X_i$ to $X.B$. The source of such a path must belong to either $X_i.A$ or $X_i.B$, by definition of profiles, and it cannot belong to $X_i.A$ because $A$ and $B$ are two different components.

It follows that $v \in X_i.B$, which means that $v$ is in the last part of the local order at $X_i$, and therefore also in the last part of the global order, among the parts that are contained in $X_i$. Since $w$ is in a red part, and it is later in the local order, it follows that the red part of $w$ must be the one that corresponds to prefix $\{X_1, \dots, X_i\}$, and not any later part, which would be excluded by Claim A.37. Therefore, the distance between the parts is at most one.

3) A symmetric argument works when the earlier vertex is red and the later vertex is black.

4) Suppose now that both vertices are black, i.e. both belong to children $X_i$ and $X_j$, with $i < j$. By Claim A.37, these children are consecutive, i.e. $j = i + 1$. By the same reasoning as in the previous cases, we know that the earlier vertex belongs to the last part of $X_i$, and the later vertex belongs to the first part of $X_j$. These parts are at distance one or two in the global order, since the only part between them is the red part corresponding to prefix $\{X_1, \dots, X_i\}$. (This part might be empty, leading to a distance of one.) $\square$

<figure><img src="image_35.png" /></figure>

A corollary of the above claim is that the linearisations have bounded width.

**Claim A.42.** *The linearisations corresponding to the global orders have bounded width.*

*Proof.* We need to show that there is a constant upper bound on the rank of prefixes in the global order. By the above claim, the edges which leave such a prefix must come from the last two parts in the prefix. Therefore, the rank of the prefix is at most the square of the width of the decomposition. $\square$

<figure><img src="image_36.png" /></figure>

This completes the proof of the lemma.

<figure><img src="image_37.png" /></figure>

## APPENDIX TO SECTION V

Previously in the appendix, we have proved the Dichotomy Lemma for uniform tree decompositions which have only local edges. In this part of the appendix, we present the remaining supplementary material for Section V, which deals with tree decompositions that have some non-local edges.

*The definition of entanglement:* We begin with the following lemma, which shows that the universal quantifiers in the definition of entanglement can be replaced by existential ones.

**Lemma A.43.** *In a uniform tree decomposition, for every supercolours $A$ and $B$, possibly equal to each other, we have the implication $1 \Rightarrow 2$ for the following conditions:*

1) for some fixpoint colour $a \in A$ and some context $X \subset Y$ in the class, there is an edge from port $a$ to some vertex with supercolour $B$ in $Y \setminus X$.

2) for every fixpoint colour $a \in A$ and every context $X \subset Y$ in the class, there is an edge from $a$ to some vertex with supercolour $B$ in $Y \setminus X$.

*Proof.* The proof follows the same lines as the proof of Lemma A.16. Let us say that fixpoint colour $a \in A$ is good in a context $X \subset Y$ if it has an edge to some vertex with supercolour $B$ in $Y \setminus X$. In this terminology, we want to show that if some fixpoint $a \in A$ is good in some context, then every fixpoint $a \in A$ is good in every context. We first prove an intermediate condition.

**Claim A.44.** *If colour $a$ is good in some context, then it is good in all contexts.*

*Proof.* This is because "being a context where $a$ is good" is an ideal, and so we can use Lemma A.5. $\square$

<figure><img src="image_38.png" /></figure>

Let $a$ be a fixpoint colour that satisfies condition 1 in the statement of the lemma. We will now show that every other fixpoint colour in $A$ satisfies condition 1. Together with the above claim, this will imply condition 2. Consider such a fixpoint colour $a' \in A$. Since $a$ is fixpoint, there is some context $X \subset Y$ in which colour $a'$ is mapped by the recolouring to $a$. By the claim, $a$ is good in this context. If we would compose this context with itself, then $a'$ would be good in it. Since the $q$-theory is idempotent, it follows that in this context $a'$ is good. By the claim, $a'$ is good in all contexts.

Note that in this, we do not use the assumption that $a'$ is a fixpoint colour. Therefore, the implication $1 \Rightarrow 2$ would continue to hold if we removed the word "fixpoint" from condition 2. However, since we want the two conditions to be equivalent, we restrict attention to fixpoint colours. $\square$

<figure><img src="image_39.png" /></figure>

In the above lemma, we showed that one could replace universal quantifiers by existential ones. The opposite implication should be easier. However, it could potentially fail for trivial reasons, namely it could be the case that there is no vertex in supercolour $B$ that is introduced by the context. The following lemma shows that such trivial reasons will not arise in any class of interest.

**Lemma A.45.** *Consider a uniform class of tree decompositions, which contains at least one non-linear tree decomposition, i.e. a tree decomposition where some two nodes that are not disjoint. Then for every supercolour $A$:*

(a) every node contains at least one vertex from $A$; and
(b) every context introduces at least one vertex in A.

*Proof.* Note the asymmetry: for the nodes, the vertices are in the node, which means that they are introduced in the node or one of its descendants. For the contexts, we make the stronger conclusion.

The item about nodes is an immediate consequence of the fact that all nodes have the same theory, and in particular the same set of colours. Consider now the second item. Choose some context $X \subset Y$ such that there is a node $Z \subset Y$ that is disjoint with $X$. Such a context can be found in any non-linear tree decomposition. Since the node has $Z$ contains vertices in all supercolours, and these vertices are introduced in from the point of view of the context $X \subset Y$, it follows that this context satisfies the condition in the claim. By uniformity of theories of contexts, all other contexts will also satisfy the condition. (Because the condition is an ideal.) □

*Proof of the Normalisation Lemma.* The main observation in the following claim.

**Claim A.46.** For every supercolours A and B we have either:

1) entanglement in some direction: $A \times B$ or $B \times A$; or

2) for every two vertices with supercolours A and B, respectively, that are introduced in non-nearby nodes, they are not connected by an edge; or

3) for every two vertices with supercolours A and B, respectively, that are introduced in non-nearby nodes, they are connected by an edge.

*Proof.* We say that there is a *yes*-connection from supercolour A to supercolour B if condition 1 from Lemma A.43 are satisfied. We say that there is a *no*-connection from A to B if there is a *yes*-connection after complementing the edge relation (it would be enough to do the *AB*-superflip, since we only talk about edges between supercolours A and B).

Suppose that there is a yes-connection from $A$ to $B$, and a no-connection from $B$ to $A$. By Lemma A.43, we get an entanglement $A \times A$. Similarly, if there is a no-connection from $A$ to $B$ and a yes-connection from $B$ to $A$, then we get an entanglement $B \times A$. Otherwise, if we cannot get such an entanglement, then there is some $\alpha \in \{\text{yes, no}\}$ such that we do not have an $\alpha$-connection from $A$ to $B$, and we do not have an $\alpha$-connection from $B$ to $A$. Depending on the choice of $\alpha$, we will get the second or third alternatives in the claim.

Suppose that $\alpha$ is “yes”. Consider a node $X$. By the assumption that we do not have a yes-connection, it follows that in the context $X \subset \text{root}$ there is no edge from colour $A$ in the complement of $X$ to any vertex of the form $X.b$ where $b$ is a fixpoint colour in $B$. For every proper descendant of $X$, every vertex in that descendant has a fixpoint colour in the node $X$. Therefore, it follows that there is no edge from supercolour $A$ in the complement of $X$ to any vertex from supercolour $A$ in a proper descendant of $X$. This implies that second alternative in the claim.

The argument is the same if we do not have a no-connection, in which case we get the third alternative. □

For every supercolours $A$ and $B$, we apply the above claim, yielding one of the three alternatives. If we apply the *AB*-superflip, then we the second alternative is swapped with the third alternative for $A$ and $B$, and there is no effect on the for other pairs of supercolours (except the same pair in a different order, namely $B$ and $A$). Therefore, up to superflips, we can assume that the third alternative never holds. This gives us the conclusion of the lemma. □

### I. Covering Lemma

In this section, we introduce a tool that will be used to show that a class transduces all trees, which is called the Covering Lemma.

*Obstruction:* The main notion in the covering lemma is that of an obstruction. This is a binary graph pattern which has two properties, formalised in Definition A.47 below. The first property is that the obstruction generates a class that transduces all trees, regardless of the choice of initial graph in the template. The second condition, which is a minor technical assumption, is that the obstruction does not change colours, i.e. if we apply it to some arguments, then the vertices from the arguments will continue to have the same colours in the output.

**Definition A.47 (Obstruction).** An obstruction with $k$ colours is a binary graph term of type $k \times k \rightarrow k$ with the following properties:

1) for every template that arises from the obstruction by choosing some initial graph, the class of graphs generated by the template transduces all trees;

2) for both arguments in the obstruction, the corresponding recolouring is the identity.

In the definition of obstructions, the trees (i.e. acyclic graphs) are transduced using MSO. In fact, in all obstructions that we consider in this paper, the trees will be transduced using first-order logic. Let us give some examples of obstructions.

**Example 10.** Consider the template from Example 4

<figure><img src="image_40.png" /></figure>

This template generated the comparability graphs of binary trees, from which one can transduce all trees. It is not hard to see that trees will continue to be transduced even if we change the initial graph; this is because any other extra vertices in a new initial graph can be deleted. Since there is only one colour, the technical condition on recolourings is satisfied. Therefore, the binary term

<figure><img src="image_41.png" /></figure>
from the template is an obstruction. □

**Example 11.** Consider the following binary graph term

<figure><img src="image_42.png" /></figure>

This is an obstruction. The idea is that the neighbourhoods of the red vertices, which are sets of blue vertices, follow a hierarchical containment discipline, as in the definition of trees, and therefore the tree structure can be recovered. □

**Example 12.** Let us give a non-example of an obstruction. Consider the template

<figure><img src="image_43.png" /></figure>

from Example 5 that was used to generate child graphs of trees. This is not an obstruction, because there is a non-identity recolouring: the blue vertices become red after applying the binary operation. □

**Lemma A.48.** If C covers D then also C transduces D.

*Proof.* The operations in the definition of covering a template are MSO transductions. □

**The Covering Lemma:** The Covering Lemma, which will be stated below, says that a sufficient condition for transducing all trees is that there is a finite set (of possibly more than one) obstructions such that for every “piece” of the tree decomposition, one of the binary terms from the set is ‘covered’ by it. We begin by explaining the meaning of the quoted terms.

A “piece” of a tree decomposition is formalised using multicontext, as defined at the end of Section D. We will care about multicontexts of arity two, i.e. nodes $X_1, X_2 \subset X$ such that $X_1$ and $X_2$ are disjoint. We use the name *bicontext* for such multicontexts. For technical reasons, we will want the bicontextts to be *separated*, in the following sense; there is some node $Y$, called a *separating node*, which is strictly between $X$ and its two descendants in the bicontext, i.e.

$$X_1 \cup X_2 \subset Y \subset X.$$

There could be several choices for the separating node; if disambiguation is needed, then one can use the closest common ancestor of the two arguments $X_1$ and $X_2$.

The most complicated notion involves “covering”. This idea is that the obstruction can be obtained by superflips, contractions of local colours, and vertex deletions. Here, a

contraction of local colours is a contraction of any connected set where all vertices use local colours. The notion of covering is only applicable to normalized tree decompositions, where we expect local colours to satisfy the local edge property.

**Definition A.49 (Covering).** Consider a bicontext inside a normalized uniform tree decomposition. A binary term is covered by this bicontext if it can be obtained from the induced graph term of the bicontext by any sequence of the following transformations:

* entangled superflips, i.e. AB-superflips where $A \times B$;

* contracting a set that uses only local colours;

* deleting vertices.

We say that a tree decomposition covers a set of $O$ of obstructions if every separated bicontext covers at least one of the obstructions. Note that there is some nondeterminism here, namely that both the obstruction, and the superflips required to cover it, could depend on the bicontext. We are now ready to state the Covering Lemma.

**Lemma A.50.** (Covering Lemma). Let $\mathcal{T}$ be a uniform class of tree decompositions, and let $\mathcal{O}$ be a finite set of obstructions such that:

1) $\mathcal{T}$ has unbounded Strahler number.

2) every tree decomposition in $\mathcal{T}$ covers $\mathcal{O}$.

Then $\mathcal{T}$ transduces all trees.

*Proof.* We begin by showing that, without loss of generality, assumption 2 can be strengthened to saying that every bicontext, not necessarily separated, covers some obstruction from $\mathcal{O}$. This is done by taking appropriate tree minors. Define a separated minor of a tree $T$ to be a tree minor $S \le T$ which is a binary tree, and such that for every node $X \in S$, all $S$-children of $X$ are contained in the same $T$-child of $X$. It is not hard to see that if a class of trees has unbounded Strahler number, then the same is true for its separated minors. Let then $S$ be the sub-decompositions of $\mathcal{T}$ that are obtained by restricting the tree to some separated minor. The new class also has unbounded Strahler number, and every bicontext in $S$ corresponds to a separated bicontext in $\mathcal{T}$.

Thanks to the above reasoning, we will now assume a stronger version of assumption 2, namely that every bicontext, not necessarily separated, covers some obstruction from $\mathcal{O}$. We now move to the essential difficulty in the lemma, which is that there is some nondeterminism in the covering assumption: different bicontextts will cover different operators, and might use different superflips to do this. Before resolving this difficulty, we observe that when applying the operations in the definition of covering, we can start with superflips.

**Claim A.51.** If we modify the Definition A.49 by requiring that superflips are applied before contractions and vertex deletions, then the resulting definition is equivalent to the original one.

*Proof.* Clearly vertex deletions commute with superflips. Also, since the superflips affect only non-local colours, they
commute with the contractions, since the contractions concern only local colours. □

Since superflips commute with each other, and applying the same superflip twice is the same as not applying it at all, the initial sequence of superflips from the above claim can be seen as a set of superflips, i.e. a set of entangled pairs of supercolours. We will track this set, using a *profile*, which is defined to be a pair consisting of:

1) an obstruction from $O$;

2) a set of superflips.

A profile is *realized* by a bicontext if the obstruction from the first item is covered using the superflips from the second item. More formally, the obstruction is obtained applying the superflips from the second item (in whichever order), and then doing a sequence of local contractions and vertex deletions. We know that every bicontext has some profile. The following claim will allow use to extract sub-decompositions so that the same profile is always used.

**Claim A.52.** There is some profile $\sigma$ such that the class

$$ \{T \mid T \text{ is a sub-decomposition of } \mathcal{T} \text{ where all bicontext s realize profile } \sigma\} $$

has unbounded Strahler number.

*Proof.* We view a profile as a side constraint, which consists of pairs of disjoint nodes $X_1, X_2$ such that if we define the top node $X$ to be the closest common ancestor of $X_1$ and $X_2$, then profile is realized by one of the bicontext

$$ X_1, X_2 \subset X \text{ or } X_2, X_1 \subset X. \quad (7) $$

In the above definition, we need to use the two orders between $X_1$ and $X_2$, since side constraints are commutative, while profiles are not, since the operators might make a distinction between the left and right arguments. This is easily seen to be a side constraint, since the local covering will persist even if we move one of the nodes $X_1$ or $X_2$ deeper down in the tree (here we use the assumption that the recolourings in an obstruction are the identity). By applying Lemma A.7 to the side constraints corresponding to all finitely many possible profiles, we see that either:

1) for some profile $\sigma$, the class $\mathcal{T}$ has minors of unbounded Strahler number where every two disjoint nodes belongs to the side constraint corresponding to $\sigma$; or

2) one can associate to each tree decomposition from $\mathcal{T}$ a split, such that the splits have bounded height, and on each layer of the split, no pair of nodes belongs to any of the side constraints.

The second option is impossible, because every bicontext has some profile. Therefore, the first option must hold. To complete the proof of the claim, we observe that if two nodes $X_1$ and $X_2$ satisfy the side constraint corresponding to a profile $\sigma$, then for every node $X$ which contains both $X_1$ and $X_2$, one of the two bicontext in (7) will realize the profile $\sigma$. By definition of the side constraint, this happens if $X$ is chosen to be the closest common ancestor of the two

nodes. Also, if we move the node $X$ higher up in the tree, the profile continues to be realized, since we can simply delete more vertices. □

Let $\sigma$ be the profile from the above claim, and let $\mathcal{T}_{\sigma}$ be the sub-decompositions of $\mathcal{T}$ in which all bicontext realize the profile $\sigma$. By the above claim, one of the classes $\mathcal{T}_{\sigma}$ has unbounded Strahler number. In this class $\mathcal{T}_{\sigma}$, every bicontext covers the same obstruction, and uses the same superflips to cover it. In particular, the superflips can be applied once, to the entire tree decomposition, instead of applying them individually at each bicontext. Since a superflip is a special case of an MSO transduction, we can assume without loss of generality that there are no superflips in the profile.

Summing up, we have reduced the lemma to the special case when the set of operators contains only one obstruction, and every bicontext, not necessarily separated, covers this obstruction without using any superflips. It remains to prove this special case.

Let us first deal with the initial graph of the template. By definition of obstructions, we can choose any initial graph we want. We choose it to be as small as possible, i.e. it has only one vertex per colour. The induced graphs of this kind can be read from the MSO theory, and therefore by uniformity<fnref n="6" /> we know that there is some initial graph that appears as an induced subgraph of every node in the class of tree decompositions $\mathcal{T}$. We use this graph as the initial graph.

The only remaining difficulty is the contractions. We first observe that when the obstructions are covered, only a constant number of such contractions is needed. This is because the obstruction has constant size, and it only makes sense to use contractions which contribute something to the obstruction. The second observation is that the contractions can be done in parallel, as long as the corresponding bicontext s are far enough. This is because, by normalisation, all edges connecting local colours must have their endpoints introduced in nearby nodes. Therefore, if we take bicontext s that are far enough, e.g. we skip every second level, then the contractions of local paths will be independent. Therefore, the graph generated by the template will be obtained from the underlying graph of the tree decomposition by a constant number of independent contractions, followed by vertex deletions. Since these are MSO transductions, we get the conclusion of the Covering Lemma. □

## J. Orientations

In this part of the appendix, we give supplementary material to Section V-C, mainly a proof of the Orientation Lemma.

<footnote n="6">⁶Formally speaking, this argument would require the quantifier depth to depend on the number of colours in the obstruction. However, we will only apply the Covering Lemma to obstructions with at most 5 colours, and therefore the fixed quantifier depth of $q = 9$ will be good enough for the argument.</footnote>
We begin by proving Fact V.7, which shows that an orientation can only arise if the entanglement relation is symmetric and irreflexive.

**Proof of Fact V.7.** Let us first clarify an edge case concerning the first item in the definition of orientations: when $A = B$, then we count the conditions $A \to B$ and $B \to A$ as two conditions, so it cannot be the case that exactly one of them holds. In particular, if there is an orientation, then the entanglement relation must be irreflexive, i.e. we cannot have self-entanglement $A \not\times A$.

Let us now prove symmetry. Toward a contradiction, suppose that we would have $A \times B$ but not $B \times A$. Then an orientation would be impossible, since the first item would require one of the conditions $A \to B$ or $B \to A$ to be true, while the second item would require none to be true. $\square$

We now move to the Orientation Lemma, which shows that the Dichotomy Lemma can be reduced to the special case of classes which are uniform, normalized and oriented. The main ingredient in the proof is the following result, which uses splits of bounded height to reduce to oriented tree decompositions.

**Lemma A.53.** Let $\mathcal{T}$ be a uniform class of tree decompositions, which does not transduce all trees. Then to each tree decomposition in $\mathcal{T}$ one can associate a split so that:

(a) the heights of the splits are bounded;

(b) all layers of the splits are oriented tree decompositions.

**Proof of the Orientation Lemma.** Before proving the lemma, we clarify a point about item (b) in the conclusion of the lemma. In the definition of an oriented tree decomposition, there is a quantification over recolourings that appear in the tree decomposition. Therefore, if we take a layer of a split, then the corresponding sub-decomposition might have fewer recolourings that appear in it, and for this reason it might be easier for the sub-decomposition to be oriented. This will be leveraged in the proof below.

Since $\mathcal{T}$ is uniform, all tree decompositions in $\mathcal{T}$ have the same notion of entanglement on supercolours. We will be interested in a finite set of Strahler constraints, which correspond to entangled pairs.

**Definition A.54.** For a tree decomposition in $\mathcal{T}$, define the yes-constraint of an entangled pair $A \times B$ to be the set of pairs of disjoint nodes $X_1$ and $X_2$ such that

$$ (v \in X_1.A \text{ and } w \in X_2.B) \text{ or } (v \in X_1.B \text{ and } w \in X_2.A) \\ \Downarrow \\ \text{vw is an edge} $$

holds for every vertices $v$ and $w$. The no-constraint is defined similarly, except that the conclusion of the implication says "is not an edge".

Each of the constraints in the above definition is easily seen to be a Strahler constraint, because moving the nodes $X_1$ or $X_2$ lower in the tree preserves the defining property.

This gives us a family of Strahler constraints, one for each entangled pair $A \times B$ of supercolours and every $\gamma \in \{\text{yes}, \text{no}\}$. By applying Lemma A.7 to all of these constraints, we get either:

(a) for some Strahler constraint in the family, there are tree minors of $\mathcal{T}$ that have unbounded Strahler number and in which all disjoint pairs belong to the Strahler constraint; or

(b) to each tree decomposition in $\mathcal{T}$ one can associate a split so that:

* the heights of the splits are bounded;

* on each layer, no pair of nodes belongs to any of the Strahler constraints.

We will show that the first case cannot happen, because otherwise all trees would be transduced, and that the conclusion of the lemma holds in the second case. In the first case, we will use the Covering Lemma, with the set of obstructions being

<figure><img src="image_44.png" /></figure>

These obstructions were already discussed in Examples 10 and 11.

**Case (a):** Assume that for some $\gamma$ and entangled pair $A \times B$ the class

$$ S \text{ is a tree minor of some tree decomposition} \\ S = \{S \mid \begin{array}{l} \text{in } \mathcal{T}, \text{ such that all disjoint pairs in } S \text{ belong} \\ \text{to the Strahler constraint for } \gamma \text{ and } A \times B \end{array} \} $$

has unbounded Strahler number. We will show that this case cannot happen, because otherwise $S$, and therefore also $\mathcal{T}$, would cover some regular branching class, contradicting the assumptions of the lemma. By Lemma A.10, we know that there is some recolouring $e$ such that

$$ S_e = \{S \mid S \text{ is a sub-decomposition of } S \text{ where} \\ \text{all contexts have recolouring } e \} $$

has unbounded Strahler number. Since $S_e$ consists of sub-decompositions of $S$, we know that all disjoint pairs of nodes belong to the Strahler constraint corresponding to $\gamma$ and $A \times B$. We will use the Covering Lemma, with the obstruction being the one illustrated above, to show that $S_e$, and therefore also $\mathcal{T}$, covers some regular branching class. Let us check the assumptions of the Covering Lemma. Assumption 1 requires that $S_e$ has bounded Strahler number; this was proved in Lemma A.10. Let us now prove assumption 2, which says that one of the obstructions is covered by every separated bicontext. In fact, we will show that always the same obstruction is covered, depending on whether $A = B$. This means that we will not use the full strength of the
Covering Lemma, which allows some nondeterminism in the choice of the covered obstruction.

Consider a separated bicontext $X_1, X_2 \subseteq X$ in a tree decomposition from $\mathcal{S}$. We will show that one of the above two operators is covered, depending on whether $A = B$.

* Suppose that $A = B$. Let $a$ be the image of $A$ under the shared recolouring $e$. We only prove the case when $\gamma$ is "no", with the "yes" case being symmetric. Because $\gamma$ is "no", there is no edge from $X_1.a$ to $X_2.a$. Let $Y$ be the separating node for the bicontext, i.e.

$$X_1 \cup X_2 \subseteq Y \subseteq X.$$

Since $A \times A$ is an entangled pair, we know that in the context $Y \subset X$ there is some vertex in $X \setminus Y$ that has supercolour $A$, and is connected to colour $a$ of $Y$. (In the "yes" case we would use a vertex that is not connected to colour $a$, which is also bound to exist since $A \times A$ is an entanglement.) In particular this vertex is connected to colour $a$ in both $X_1$ and $X_2$. We only keep that vertex in the bicontext, and delete the others, leading to the first obstruction

<figure><img src="image_45.png" /></figure>

* Suppose now that $A \neq B$. Let $a$ and $b$ be the images, under the recolouring $e$, of the two supercolours. Observe first that if either $A \times A$ or $B \times B$, then we would have the first case. Therefore, we can assume that neither $A \times A$ nor $B \times B$. As in the previous case, consider the separating node $Y$. Since $a \times b$, we know that there is some vertex in $X \setminus Y$ that has supercolour $A$, and which is connected to $Y.b$. Since $A \times A$ does not hold, the normalisation assumption tells us that this vertex is not connected to colour $Y.a$. Therefore, the bicontext covers the following obstruction:

<figure><img src="image_46.png" /></figure>

**Case (b):** Assume that for each tree decomposition in $\mathcal{T}$ there is a split so that:

* the heights of the splits are bounded;

* on each layer, no pair of nodes belongs to any of the Strahler constraints.

We will show that $\mathcal{T}$ satisfies the second item in the conclusion of the lemma. The general idea is that we will further refine the split from the assumption, so that it has fewer recolourings, which will make it easier for the layer to be oriented.

Consider a layer $\mathcal{S}$ of the splits described above. Since the notions of orientation and child depend on the chosen tree

structure, and we consider several such structures, we will talk about $\mathcal{S}$-children, or $\mathcal{S}$-orientations below, to make it clear which structure is considered. To each node $X$ on this layer, define its *profile* to be the set

$$ \{ \text{recolouring of } Y \subset X \mid \begin{array}{l} Y \text{ is a node of } \mathcal{S} \text{ that is a} \\ \text{proper descendant of } X \end{array} \}. $$

Consider some profile $\Pi$. If we take any sub-decomposition of $\mathcal{S}$ that uses only nodes with profile, then the recolourings of that sub-decomposition will be contained in $\Pi$. The following claim shows that such a sub-decomposition will be oriented.

**Claim A.55.** Let $\mathcal{S}$ be a tree decomposition such that no pair of nodes belongs to any of the Strahler constraints defined in Definition A.54. Let $X_1$ and $X_2$ be two disjoint nodes in $\mathcal{S}$ that have the same profile $\Pi$. Then for every recolourings $e_1, e_2 \in \Pi$, the relation

$$ A \to B \stackrel{\text{def}}{=} \text{ there is an edge from } X_1.e_1(A) \text{ to } X_2.e_2(B) $$
is an orientation.

**Proof.** Consider an entangled pair of supercolours $A \times B$. By definition of the profiles, there must be some nodes $Y_1$ and $Y_2$ such that $Y_1 \subset X_1$ and $Y_2 \subset X_2$ are contexts with profiles $e_1$ and $e_2$. Because the pair $Y_1$ and $Y_2$ does not belong to the no-constraint for $A \times B$, it follows that there must be an edge:

$$ \text{from } Y_1.A \text{ to } Y_2.B \quad \text{or} \quad \text{from } Y_1.B \text{ to } Y_2.A. $$

This implies that there must be an edge of the form

$$ \begin{array}{c} \text{from } X_1.e_1(A) \text{ to } X_2.e_2(B) \\ \text{this implies } A \to B \end{array} $$

or of the form

$$ \begin{array}{c} \text{from } X_1.e_1(B) \text{ to } X_2.e_2(A) \\ \text{this implies } B \to A \end{array} $$

Furthermore, we cannot have both $A \to B$ and $B \to A$, since otherwise the pair $Y_1$ and $Y_2$ would satisfy the yes-constraint. $\square$

<figure><img src="image_47.png" /></figure>

By the above claim, if we take a sub-decomposition of $\mathcal{S}$ by keeping only nodes with a given profile, then that sub-decomposition will be uniform. We can view the profiles as a split, by using an arbitrary total order on profiles. For this split, each layer is an oriented tree decomposition. This completes the proof of the lemma. $\square$

<figure><img src="image_48.png" /></figure>

Using the above lemma, we prove the Orientation Lemma, which says that the Dichotomy Lemma can be reduced to the case where all tree decompositions are oriented.

**Proof of the Orientation Lemma.** Suppose that we can prove the Dichotomy Lemma under the conditions in the Orientation Lemma. Let us now prove it for the general case. Consider
then a class of tree decompositions $\mathcal{T}$ as in the assumptions of the Dichotomy Lemma. Let us assume that

$$ \mathcal{T} \text{ does not transduce all trees,} \qquad (8) $$

since otherwise, the conclusion of the Dichotomy Lemma would be satisfied. To prove the Dichotomy Lemma, we need to show that $\mathcal{T}$ has linearisations of bounded width. By Lemma IV.7, we can assume that

$$ \mathcal{T} \text{ is uniform.} \qquad (9) $$

By the Normalisation Lemma, we can assume that

$$ \text{all tree decompositions are normalised.} \qquad (10) $$

If $\mathcal{T}$ has no entangled pairs of supercolours, i.e. it has only local colours, then it has only local edges by normalisation, since all pairs of supercolours satisfy the second condition in the conclusions of the Normalisation Lemma. In this case, the Dichotomy Lemma was proved in Section E.

We are left with the case where

$$ \text{there is at least one entangled pair.} \qquad (11) $$

By the Orientation Lemma, there are splits of bounded height such that the layer sub-decompositions are oriented. By Lemma A.8, it is enough to prove that the layers have linearisations of bounded width. Restricting the class to layers does not break any of the assumptions (8)–(11). Therefore, we have reduced the Dichotomy Lemma to the case where all conditions (8)–(11) hold, plus

$$ \text{all tree decompositions are oriented.} \qquad (12) $$

If the Strahler number is bounded, then we get linearisations of bounded width by Lemma A.26. Therefore, we can also assume that

$$ \text{the Strahler number is unbounded.} \qquad (13) $$

This way, we have collected all of the conditions in the Orientation Lemma, and finished the reduction. $\square$

### K. Bipolar Orientations

*Proof of the Bipolar Lemma.* When proving the Bipolar Lemma, we use an alternative characterisation of having bipolar orientations, which is more local because it looks at only four supercolours at a time. Consider two entangled pairs $A \times B$ and $C \times D$. (We must have $A \neq B$ and $C \neq D$, because entanglement is irreflexive, but there could be other equalities, and also other entanglements.) We say that these are *oriented in the same direction* by an orientation $\rightarrow$ if

$$ A \rightarrow B \text{ iff } C \rightarrow D. $$

Otherwise, we say that they are *oriented in opposite directions*. This notion depends on the order in the pairs, i.e. the directions will change if we replace $A \times B$ by $B \times A$. We would like the answer to the question

are they oriented in the same direction?

to be independent of the choice of orientation, as expressed in the following definition.

**Definition A.56.** Consider two entangled pairs $A \times B$ and $C \times D$. We say that they are oriented consistently if either:

1) for every orientation, they are oriented in the same direction; or

2) for every orientation, they are oriented in opposite directions.

The following claim shows that consistent orientations are an equivalent way of defining bipolar orientations.

**Claim A.57.** The class $\mathcal{T}$ is polarized if and only if every two entangled pairs are oriented consistently.

*Proof.* For the right-to-left implication, we observe that if all pairs are oriented consistently, then an orientation is uniquely determined by how it orients some fixed entangled pair $A \times B$. Therefore, there are two possible orientations, depending on whether this pair is oriented as $A \rightarrow B$ or $A \leftarrow B$.

For the left-to-right implication, we observe that if two entangled pairs are oriented in the same direction by an orientation $\rightarrow$, then the same will be true for the opposite orientation. Therefore, if there are only two possible mutually opposite orientations, then the above equivalence will hold for all orientations or none, thus proving the left-to-right implication. $\square$

By the above claim, to prove the conclusion of the Bipolar Lemma, it remains to show that every two entangled pairs are oriented consistently.

*Entanglement graph:* A simple consequence of the assumption on unbounded Strahler number is that there is some pair of disjoint nodes (we will use the full strength of the assumption later on). Since the class has oriented tree decompositions, this pair has some corresponding orientation (for some arbitrarily chosen recolourings). Therefore, there exists at least one orientation. By Fact V.7, the entanglement relation must be irreflexive and symmetric. Therefore, it is meaningful to view it as graph.

**Definition A.58 (Entanglement Graph).** The entanglement graph of a uniform class of tree decompositions is the graph where vertices are supercolours, and edges represent entanglement.

The entanglement graph is not necessarily well-defined, but as we have remarked above, it is well-defined under the conditions from the Orientation Lemma. In the proof below, we will discuss connectivity in the entanglement graph.

The proof will have two parts. In the first part, we show that for every connected component in the entanglement graph, entangled pairs in that component are consistently oriented. In the second part, we will show that connected components are also consistent with each other.
*One connected component of the entanglement graph:* The first part of the proof studies what happens in one connected component of the entanglement graph. The essential question is about adjacent edges, i.e. entangled pairs of the form $A \times B$ and $B \times C$. The proof strategy is as follows. We will first show that a violation of consistent orientations leads to certain patterns appearing in contexts from the tree decompositions. By uniformity, these patterns will appear in all contexts. These patterns will ensure that the class covers a finite set of obstructions, and so the Covering Lemma could be used to contradict the condition 1 in the Orientation Lemma.

The following claim identifies the patterns.

**Claim A.59.** Assume that $A \times B$ and $B \times C$ are not oriented consistently, and let $a \in A$ and $c \in C$. For every context $X \subset Y$ one can find vertices $v_1$ and $v_2$ which are introduced in the context with colour $B$, such that the following hold (see picture 2):

$v_1$ has a non-edge to $X.a$ and $v_1$ has an edge to $X.c$;

$v_2$ has an edge to $X.a$ and $v_2$ has an edge to $X.c$.

*Proof.* Observe a certain asymmetry in the conclusion of the claim: we do not have control over which particular colour from $B$ will be used by the vertices $v_1$ and $v_2$, but we can enforce the connections to any chosen colours $a \in A$ and $c \in C$. Here is a picture of these vertices:

<figure><img src="image_49.png" /></figure>

We first observe that if we can prove the claim for some recolouring, then we can prove it for every recolouring. Indeed, suppose that the statement of the claim is true for some recolouring $e$. Choose some unary graph terms $E$ which has recolouring $e$. If we compose $E$ with itself, then the argument of the right $E$ will be recoloured by $e$, and thus using the witnesses from the left copy will do the trick. (This argument shows that we prove in fact a stronger version of the claim, where the witness vertices do not depend on the choices of $a \in A$ and $c \in C$.)

Let us now find the vertices from the conclusion of the claim. From the assumption that $A \times B$ and $B \times C$ are not oriented consistently, we know that they are oriented in the same direction for some orientation $\rightarrow_1$, and in opposite directions for some other orientation $\rightarrow_2$. Here is a picture:

<figure><img src="image_50.png" /></figure>

Consider the first orientation $\rightarrow_1$. It arises for some pair $(X_1, e_1)$ and $(X_2, e_2)$, where $X_1$ and $X_2$ are disjoint nodes and $e_1$ and $e_2$ are recolourings. If we forget about argument $X_1$, and consider the context $X_2 \subset \text{root}$, then we get a witness of the first kind for the colours $a = e_2(A)$ and $c = e_2(C)$ if we choose $v_1$ to be any vertex from $X_1.e_1(B)$. A similar argument, but for the orientation $\rightarrow_2$, gives us a witness for $v_2$. $\square$

Using the patterns from the above claim, we will be able to apply the Covering Lemma, thus contradicting assumption 1 of the present lemma. The following claim identifies the obstructions that will be used in the Covering Lemma.

**Claim A.60.** The following binary graph terms are obstructions:

<figure><img src="image_51.png" /></figure>

*Proof.* The same proof will work for both terms, since it does not refer to the connections between colours $a$ and $c$. Take one of the two terms. Consider a template which arises from this term, and some initial graph that has one vertex in each of the three colours, connected in some way. (This is the general case, since for initial graphs with more than one vertex in each colour, the extra vertices can be deleted by the transduction which produces trees.) A graph generated by this template arises from some binary tree, where the leaves correspond to copies of the initial term, and the non-leaves correspond to applications of the obstruction. (The binary tree is ordered, i.e. there is a notion of left/right child, since the binary graph term in the obstruction is non-commutative.)

Consider then a graph generated by the template, arising from some binary tree $T$. Each leaf of $T$ contributes three vertices to the graph, one in each colour, corresponding to the three vertices of the initial graph. Each non-leaf of $T$ contributes one vertex to the graph, in colour $b$, corresponding to the unique vertex in the graph term that is not in the arguments.

If we look at the vertices with colours $a$ and $b$, then they are organized in a half-graph. This allows us to define in $\mathbf{MSO}$, a linear order on the vertices with colour $b$, call this order $\leq_a$. This order corresponds to a depth-first traversal of the tree, where the vertex with colour $b$ that arises from a non-leaf node appears before both of its subtrees.

By considering colours $b$ and $c$, we get another order on vertices with colour $b$, call it $\leq_c$. This order corresponds to a depth-first traversal of the tree, where the vertex with colour $b$ that arises from a non-leaf node appears after, and not before, both of its subtrees.

We have access to both of these orders. Using them, we can recover the original tree structure with an $\mathbf{MSO}$
transduction, as follows. The transduction begins by guessing
which vertices arise from leaves, and which ones arise from
non-leaves. It then defines the two orders $\leq_a$ and $\leq_c$. Consider
now some vertex $v$ that has colour $b$, and which arises from
a non-leaf. It is not hard to see that the set

$$
\{u \mid u \text{ has colour } b, \text{ arises from a leaf, and } v \leq_a u \leq_c v \}
$$

describes exactly the vertices that have colour *b* and arise
from leaves in the subtree of the node from which *v* arises.
This way we can define the branching structure of the
original binary tree.

Observe that in this proof, we did not really need the
full power of MSO, and a first-order transduction would be
enough. This will continue to be the case in the future. □

We are now ready to establish consistent orientations for
overlapping entangled pairs.

**Claim A.61.** Every overlapping pairs $A \times B$ and $B \times C$ are oriented consistently.

*Proof.* The proof is by contradiction. Suppose that $A \times B$ and $B \times C$ are not oriented consistently. We will show that $\mathcal{T}$ transduces all trees, thus contradicting assumption 1 of the present lemma. This will be done by using the Covering Lemma. Thanks to the obstructions from Claim A.59, we will be able to apply the Covering Lemma to the terms from Claim A.60.

Let us prepare the ground for an application of the Cov-
ering Lemma. By assumption 3 of the present lemma, $\mathcal{T}$ has
unbounded Strahler number. By Lemma A.10, we know that
there is a recolouring $e$ such that

$$
\mathcal{T}_e = \{T \mid \begin{array}{l} T \text{ is a sub-decomposition of } \mathcal{T} \text{ where} \\ \text{all contexts have recolouring } e \end{array} \}
$$

has unbounded Strahler number. We will use the Covering
Lemma to show that $\mathcal{T}_e$, and therefore also $\mathcal{T}$, transduces
all trees. Assumption 1 of the Covering Lemma, about un-
bounded Strahler number, is satisfied by choice of $e$. The set
$\mathcal{O}$ of obstructions will be the ones from Claim A.60. Formally
speaking, it is the terms from Claim A.60, for every possible
assignment of $a, b, c$ to colours from the class $\mathcal{T}$. Therefore,
the set $\mathcal{O}$ has more than two obstructions, but it is still a
finite set of obstructions. It remains to prove assumption 2,
which says that every separated bicontext in $\mathcal{T}_e$ covers some
obstruction from $\mathcal{O}$.

Consider a separated bicontext $X_1, X_2 \subset X$ in some tree
decomposition from $\mathcal{T}_e$. Let $\to$ be the orientation of $(X_1, e)$
and $(X_2, e)$. Let $Y$ be the separating node from the definition
of a separated triple. Consider two cases, depending on
whether $A \times B$ and $B \times C$ are oriented in the same direction
by $\to$.

1) Suppose that $A \times B$ and $B \times C$ are oriented in the same direction by $\to$. Let $a, b, c$ be the images of $A, B, C$ under the recolouring $e$. Here is a picture of the situation:

<figure><img src="image_52.png" /></figure>

The dotted lines in the picture mean that there may or
may not be an edge. By flipping the supercolours *A* and
*C*, we know that either there is no edge between *a* and *c*,
or there is one edge that goes in the south-east direction,
as in the terms from Claim A.60. Consider the witness
$v_2$ from Claim A.59, applied to the context $Y \subset X$.
Like all contexts in $\mathcal{T}_e$, this context has recolouring
*e*, and therefore we can assume that the witness $v_2$
has colour *b*. (This is because composing the context
with itself gives such a witness, and the theories are
idempotent.) By keeping only this witness $v_2$, we see
that the bicontext $X_1, X_2 \subset X$ contains the following as
an induced sub-graph:

<figure><img src="image_53.png" /></figure>

By flipping the supercolours *AB* and *BC*, we get an
obstruction from *O*.

2) Suppose now that $A \times B$ and $B \times C$ are oriented in opposite directions by $\to$. Using a similar argument as in the previous case, we see that the bicontext $X_1, X_2 \subseteq X$ contains the following as an induced subgraph:

<figure><img src="image_54.png" /></figure>

After flipping the supercolours BC, we get an obstruc-
tion from O.

So far, we have proved that overlapping entangled pairs
must be oriented consistently. We now extend this result to
connected components of the entanglement graph.
**Claim A.62.** Suppose that $A \times B$ and $C \times D$ are entangled pairs that are in the same connected component of the entanglement graph. Then they must be oriented consistently.

*Proof.* Induction on the length of the path, in the entanglement graph, that connects $A$ with $C$. In the induction step, we use Claim A.61. □

*Disconnected components:* We now turn to the case of entangled pairs $A \times B$ and $C \times D$ that are in different connected components of the entanglement graph. In this part of the proof, we will use the colour connectedness assumption from the definition of uniform classes.

We proceed similarly to the case of overlapping entangled pairs. We first show that a violation of consistent orientations leads to certain obstructions appearing in contexts from the tree decompositions. Then we use these obstructions to show apply the Covering Lemma.

In the following claim, we will be interested in entangled pairs that can be connected using a path of local colours. We say that a path *uses local colours internally* if all of its vertices, except possibly the source and target, have local colours. We will be interested in such paths that connect two non-local colours. As in the discussion before the statement of the Bipolar Lemma, the existence of such paths can be expressed in MSO, and therefore it does not depend on the choice of node or tree decomposition.

**Claim A.63.** Consider entangled pairs $A \times B$ and $C \times D$ such that:

1) they are not oriented consistently;

2) there is a path from $B$ to $C$ that uses only local colours internally.

Then every context $X \subset Y$ and every recolouring $e$ has the following property:

(*) If we define $a, b, c, d$ to be the images of $A, B, C, D$ under $e$, then one can find paths $P_1$ and $P_2$ which use only vertices introduced by the context, and satisfy the conditions explained in Figure 2.

*Proof.* By Claim A.62, we know that in the entanglement graph, $A \times B$ cannot be in the same connected component as $C \times D$. In particular, we know that there are no other entanglements except the assumed ones $A \times B$ and $C \times D$. The proof is similar to Claim A.59. We only prove the existence of the path $P_1$ from condition (*), with the case of $P_2$ being treated in the same way. Using the same kind of argument as in that claim, we show that if the path $P_1$ from condition (*) exists for some context and some recolouring, then it also exists for every context and every recolouring. Therefore, it remains to show that this path exists for some context and recolouring.

By assumption 1 of the claim, the class witnesses both kinds of orientations:

<figure><img src="image_55.png" /></figure>

We will use the left orientation to get the path $P_1$. (The right one is used in a similar argument for $P_2$.) The left orientation must arise for some disjoint nodes and recolourings, say $(X_1, e_1)$ and $(X_2, e_2)$. We will show that the path $P_1$ from condition (*) exists in the context $X_2 \subset \text{root}$, under the recolouring $e_2$. By assumption 2 of the claim, we know that some node has a path from $B$ to $C$ that uses only local colours apart from its source and target. Since $e_1$ is a recolouring that appears in the class, then there is such a path where the source has colour $e_1(B)$ and the target has colour $e_1(C)$. As usual, by uniformity, the existence of such a path does not depend on the choice of node. In particular, the node $X_1$ has such a path. This path can be used to witness the path $P_1$ in the context $X_2 \subset \text{root}$. □

As previously, we will use the patterns from the above claim to apply the Covering Lemma. The corresponding obstruction identified in the following claim.

**Claim A.64.** The following binary graph term is an obstruction

<figure><img src="image_56.png" /></figure>

*Proof.* We use the same proof as in Claim A.60. There are two half-graphs, corresponding to $a \times b$ and $c \times d$. Each non-leaf node of the binary tree contributes three vertices, in colours $b, \ell, c$. The vertex with colour $\ell$ has only two neighbours, namely the vertices in colours $b$ and $c$ that are contributed by the same node. The vertex in colour $b$ is at the end of the subtree, and the vertex in colour $c$ is at the beginning. Since they are matched using the vertex with colour $\ell$, we can recover the tree structure. □

We now show that the patterns from Claim A.63 would necessarily lead to an application of the Covering Lemma, and so they cannot happen.

**Claim A.65.** There cannot be any entangled pairs as in the assumptions of Claim A.63.
$P_1$ satisfies the following conditions:

<figure><img src="image_57.png" /></figure>

$P_2$ satisfies conditions (i)–(iii) as above, but condition (iv) is changed to:

<figure><img src="image_58.png" /><figcaption>Fig. 2. The paths $P_1$ and $P_2$.</figcaption></figure>

*Proof.* We proceed in the same way as in Claim A.61. Suppose that $A \times B$ and $C \times D$ satisfy the assumptions of Claim A.63. Apply the claim, yielding condition (*). Using Lemma A.10, choose some recolouring $e$ such that

$$ \mathcal{T}_e = \{T \mid T \text{ is a sub-decomposition of } \mathcal{T} \text{ where all contexts have recolouring } e\} $$

has unbounded Strahler number. We will use the Covering Lemma for the obstruction from Claim A.64. (As previously, we are actually with a family of obstructions, with one for every assignment of colours.) It remains to show that this obstruction is covered by every separated bicontext in the class $\mathcal{T}_e$.

Consider such a separated bicontext $X_1, X_2 \subset X$. Let $Y$ be the separating node. Let $\rightarrow$ be the orientation of $(X_1, e)$ and $(X_2, e)$. Suppose that $A \times B$ and $C \times D$ are oriented the same way by $\rightarrow$. (The other case, when they are oriented in opposite directions, is treated in a similar way, and is left to the reader). We will use the path $P_2$ from condition (*) in Claim A.63, as applied to the context $Y \subset X$ and the recolouring $e$. Choose some local supercolour $L$ that is used by this path, and let $\ell = e(L)$. The path $P_2$ can be chosen so that it uses a vertex in colour $\ell$. In the argument below, we will contract the internal part of the path (i.e. all vertices

except the source and target, which use local colours) so that it becomes a single vertex in colour $\ell$. If we keep, in the bicontext only the three vertices from this path (the source, target, and the contracted internal part), then we get the term from Claim A.64. $\square$

Let us summarize what we know so far. We know that the following are sufficient conditions for $A \times B$ and $C \times D$, having consistent orientations:

**Claim A.62** $A \times B$ and $C \times D$ are in the same connected component of the entanglement graph; or

**Claim A.65** there is a path from $B$ to $C$ that uses only local colours internally.

In particular, if we take two connected components in the entanglement graph which are connected by a local path (i.e. there is a path that uses only local colours internally, and connects the two connected components), then all entangled pairs in the union of the two components must be oriented consistently. By the colour connectedness assumption 3 in the definition of uniform tree decompositions, we know that we can go from every connected component in the entanglement graph to every other connected component by such a path, and therefore all entangled pairs are oriented consistently. This completes the proof of the Bipolar Lemma. $\square$