Bruno Courcelle Labri
email: courcell@labri.fr

From tree-decompositions to clique-width terms

Tree-width and clique-width are two important graph complexity measures that serve as parameters in many fixed-parameter tractable algorithms. We give two algorithms that transform tree-decompositions represented by normal trees into clique-width terms. As a consequence, we obtain that for sparse graphs, clique-width is polynomially bounded in terms of tree-width. It is even linearly bounded for planar graphs and incidence graphs. These results have applications to model-checking algorithms for problems described by monadic second-order formulas, including those allowing edge set quantifications.

Introduction

Tree-width and clique-width are important graph complexity measures that occur as parameters in many fixed-parameter tractable (FPT) algorithms [START_REF] Courcelle | Graph structure and monadic second-order logic, a language theoretic approach[END_REF][START_REF] Courcelle | Linear-time solvable optimization problems on graphs of bounded clique-width[END_REF][START_REF] Downey | Parameterized complexity[END_REF][START_REF] Downey | Fundamentals of parameterized complexity[END_REF][START_REF] Fischer | Counting truth assignments of formulas of bounded tree-width or clique-width[END_REF]. They are also important for the study of graph structure and, in particular, for the description of certain graph classes by forbidden subgraphs, minors or vertex-minors. Both notions are based on certain hierarchical graph decompositions, and the associated FPT algorithms use dynamic programming on these decompositions. Many of these algorithms need input graphs of moderate tree-width or clique-width that are given with the relevant decompositions. Constructing optimal decompositions is difficult [START_REF] Arnborg | Complexity of finding embeddings in a k-tree[END_REF][START_REF] Fellows | Clique-width is NPcomplete[END_REF], however, there exist polynomial time approximation algorithms [START_REF] Bodlaender | Treewidth computations I. Upper bounds[END_REF][START_REF] Oum | Approximating rank-width and clique-width quickly[END_REF].

A related problem consists in comparing width measures in the following way. Given two width measures wd and wd ′ and a graph class C, we wish to prove graph G are nothing but MSO properties of its incidence graph Inc(G). As the clique-width of Inc(G) is linearly bounded in terms of the tree-width of G, the algorithms for the MSO model-checking of graphs of bounded clique-width can be used (in practice) for the MSO 2 model-checking of graphs of bounded tree-width. This extension is developped in [START_REF] Courcelle | Fly-automata for checking monadic second-order properties of graphs of bounded tree-width[END_REF][START_REF] Courcelle | Fly-automata for checking MSO 2 graph properties[END_REF].

Summary and main results. Section 1 reviews notation about trees and graphs. Section 2 defines our novel presentations of tree-decompositions and clique-width terms. Section 3 presents in a unified way three algorithms that convert tree-decompositions into clique-width terms. In Section 4, we obtain that cwd(G) = O(twd(G)) for planar graphs (we improve the linear bound given in [START_REF] Fomin | Rank-width and tree-width of H-minorfree graphs[END_REF]) and that cwd(G) = O(twd(G) q ) for uniformly q-sparse graphs (the graphs whose subgraphs have at most qn edges for n vertices). In Section 5, we consider q-hypergraphs (their hyperedges have at most q vertices). A q-hypergraph H can be viewed as a bipartite graph Bip(H) and we prove that cwd(Bip(H)) = O(twd(H) q-1 ). For incidence graphs, we deduce that cwd(Inc(G)) = O(twd(G)). In Section 6, we review the algorithmic applications to model-checking. In the appendix we consider the effect of minor-reducing operations on tree-decompositions defined by normal trees.

Acknowledgement: I thank I. Durand, S. Oum and M. Kanté for their useful comments.

Definitions and basic facts

Most definitions are well-known, we mainly review notation. We state a few facts that are either well-known or easy to prove.

The union of two disjoint sets is denoted by ⊎. The cardinality of a set X is denoted by |X| and its powerset by P(X).

If 0 ≤ m ≤ k, we define γ(k, m) as the number of subsets of [k] := {1, ..., k} of cardinality at most m. This number is 1 + k + ... + k m = O(k m ) for fixed m. If 1 < m < k/2, then γ(k, m) < m k m < k m /(m -1)!. We will actually use γ(k, m) for "small" fixed m and "large" variable k.

In this article, all trees, graphs and hypergraphs are nonempty and finite.

Trees

Trees are always rooted; N T denotes the set of nodes of a tree T and ≤ T its ancestor relation, a partial order on N T ; the root, denoted by root T , is the unique maximal element and the leaves are the minimal ones; p T (u) is the father (the closest ancestor) of a node u.

We denote by T ≤ (u) the set {w ∈ N T | w ≤ T u}, by T < (u) the set {w ∈ N T | w < T u} and similarly for T > (u) and T ≥ (u).

If e is an edge of T between a node u and its father w, then the tree T ′ resulting from the contraction of e is constructed as follows: we remove u and e and we make each son of u into a son of w. The root of T ′ is that of T .

Graphs

Unless otherwise specified (as in Section 5.2), we consider simple graphs, i.e., they are loop-free and without parallel edges; they are directed or not. Undefined notions are as in [START_REF] Diestel | Graph theory[END_REF]. A graph G has vertex set V G and edge set E G . If G is directed, E G can be identified with the binary, irreflexive edge relation G . We denote by G[X] the induced subgraph of G with vertex set X ∩ V G . Note that X need not be a subset of V G in order to deal easily with cases where X is a set of vertices of a graph H of which G is a subgraph.

edg G ⊆ V G × V G ;
If G is directed and x ∈ V G , then N + G (x) is the set of vertices y such that x → G y (i.e., there is an edge from x to y), N - G (x) is the set of those such that y → G x and N G (x) := N + G (x) ∪ N - G (x) is the set of neighbours of x. If G is undirected, then N G (x) is the set of neighbours of x. We extend these definitions to the case where x / ∈ V G : then N G (x) = ∅. For a set3 X, N + G (X) is the union of the sets N + G (x), x ∈ X, and similarly for N G and N - G . If G is an undirected graph, and X, Y are disjoint sets, we define Ω(X,

Y ) := {N G (x)∩Y | x ∈ X∩V G }; if G is directed, Ω(X, Y ) := {(N + G (x)∩Y, N - G (x)∩Y ) | x ∈ X ∩ V G }. If G is

Sparse graphs

A graph G is uniformly q-sparse if |E H | ≤ q |V H | for every (undirected) subgraph H of Und(G).
An undirected graph G is uniformly q-sparse if and only if it has an orientation of indegree at most q ( [START_REF] Frank | Connectivity and networks[END_REF] or Proposition 9.40 of [START_REF] Courcelle | Graph structure and monadic second-order logic, a language theoretic approach[END_REF]). Every planar graph G is uniformly 3-sparse (because

|E G | ≤ 3 |V G | -6).
An undirected graph is uniformly ⌈d/2⌉-sparse if its maximum degree is d.

We denote by S r the class of graphs G such that Und(G) does not contain a subgraph isomorphic to the complete bipartite graph K r,r . These graphs are K r,r -free with respect to subgraph inclusion and removal of orientation. Every uniformly q-sparse graph belongs to S 2q+1 , but for every r and q, there are graphs in S r that are not uniformly q-sparse (because there is a constant c such that, if r ≥ 3, there is a graph having n vertices and at least c.n 2-2/(r+1) edges, see [START_REF] Diestel | Graph theory[END_REF], Section 7.1).

2 Tree-width and clique-width

Tree-decompositions of various kinds

Tree-decompositions are well-known, but we present new definitions concerning them.

Definitions 1: Normal trees and tree-decompositions. (a) A tree T is quasi-normal for a graph G if V G ⊆ N T and the two ends of each edge of G are comparable under < T . It is normal if in addition, we have V G = N T . A depth-first spanning tree of a graph is thus normal.

(b) In a tree-decomposition (T, f) of a graph G, the tree T is always rooted, f maps N T to P(V G ) and satisfies the well-known conditions 4 . In cases where V G ⊆ N T , we will denote by f * (u) the set f (u) -{u}.

(c) A tree-decomposition (T, f ) of a graph G is normal (resp. quasi-normal ) if T is normal (resp. quasi-normal) for G and : f (u) ⊆ T ≥ (u) for every u ∈ N T , and u ∈ f (u) for every node u of T that is a vertex of G.
(d) Let a tree T be normal for a graph G. For each u ∈ V G , we define :

up G,T (u) := N G (u) ∩ T > (u), up + G,T (u) := N + G (u) ∩ T > (u) and up - G,T (u) := N - G (u) ∩ T > (u) if G is directed. f * T (u) := N G (T ≤ (u)) ∩ T > (u) = {up G,T (w) ∩ T > (u) | w ≤ T u},
and finally,

f T (u) := {u} ∪ f * T (u).
Hence, f T (u) consists of u and its ancestors that are adjacent to some vertex w ≤ T u.

If T is quasi-normal, we use the same notions and for u ∈ N T -V G , we define :

f T (u) := f * T (u).
We define the width of (G, T ) as the maximal cardinality of a set f * T (u).

Claim 1 : If T is quasi-normal (resp. normal) for a graph G, then (T, f T ) is a quasi-normal (resp. normal) tree-decomposition of this graph. The width of the tree-decomposition (T, f T ) is that of (G, T ).

2 : If (T, f) is a quasi-normal tree decomposition, then f T (u) ⊆ f (u) for all u. Proof : Consider y ∈ f T (u). If y = u, then y ∈ f(u).
Otherwise, x ≤ T u < T y for some x adjacent to y. Then, x, y ∈ f (w) for some node w. We have w ≤ T x < T y, hence, y ∈ f(u) by the connectivity condition since w ≤ T u < T y and y ∈ f (y) ∩ f (w).

Informally, if T is quasi-normal, then f T is the "minimal" mapping f such that (T, f ) is a quasi-normal tree decomposition.

Example 2 : Figure 1 shows a graph G and the tree T of a normal treedecomposition (T, f ). The function f is defined in the following table. The function f T is equal to f except that f T (g) = {c, e, g} ⊂ f(g) and f T (h) = {e, h} ⊂ f (h). The set f * T (c) contains vertex a because of the edge ae. Clearly, (T, f ) is not optimal, as (T, f T ) has smaller width (cf. Definition 1(d)).

u f (u) u f(u) a a e e, c, a b b, a g g, e, c, a c c, a h h, e, c d d, a i i, c
In further examples, we will use a linear notation for trees. The tree T of this example can be denoted by a(b, c(e(g, h), i), d) and, equivalently, by a(b, d, c(i, e(h, g)) as, in our trees, the sons of a node are not ordered.

Lemma 3 : Every tree-decomposition (T, f) of a graph G can be transformed into a normal tree-decomposition (T ′ , f ′ ) of G of no larger width.

Proof sketch (cf. [START_REF] Courcelle | Graph structure and monadic second-order logic, a language theoretic approach[END_REF], Proposition 2.67) : If (T, f ) is not normal, we first contract all edges up T (u) of T such that f (u) ⊆ f(p T (u)) (cf. Section 1.1). Then, if f (root T ) = ∅, we contract the edge between root T and one of its sons, say w (we must have f(w) = ∅). We obtain a tree T 1 (its root is that of T ) and we define f 1 as the restriction of f to N T 1 , except for the root if f (root T ) = ∅: in this case f 1 (root T ) := f(w) (where w is as above).

For each node u such that |f 1 (u)f 1 (p T1 (u))| = m > 1, we insert m -1 nodes forming a path with m edges between u and p T 1 (u); similarly, if |f 1 (root T )| = m > 1, we insert m -1 nodes below the root. We obtain a normal tree T ′ and tree-decomposition (T ′ , f ′ ) of G of same width as (T, f ). (The function f ′ is easy to define and we identify a node u with the vertex

x such that f ′ (u) -f ′ (p T ′ (u)) = {x} or f ′ (u) = {x} if u is the root.)
Hence, for studying optimal tree-decompositions, there is no loss of generality in considering only normal ones with "minimal" bags, hence of the form (T, f T ) where T is normal for G. Such a tree-decomposition can be encoded in a very compact way: the tree T is represented by the partial function p T : V G → V G (defined by pointers) or by any other appropriate data structure, the edges of G by the function up G,T (or by up + G,T and up - G,T ) and the sets f

T (u) for u ∈ N T = V G can be computed from edg G , from up G,T or from up + G,T and up - G,T , in time O(m) where m is the size of (T, f T ) defined as Σ{|f T (u)| | u ∈ N T }. Clearly, m ≤ (k + 1) |V G |
where k is the width of (T, f T ).

Definition 4 : Clean tree-decompositions. A normal tree-decomposition (T, f) of a graph G is clean if f = f T and p T (u) ∈ f (u) for every node u of T that is not the root. This is the case if T is a depth-first spanning tree. In Example 2, the decomposition (T, f T ) is clean and T is not spanning (the edge ac is not in G but a ∈ f T (c)). For another example, consider K 1,3 with vertex 1 adjacent to 2,3,4 and normal tree U = 1 → 2 → 3 → 4 with root 1. The tree-decomposition (U, f U ) is normal but not clean because the father of 4 is 3 and f U (4) = {1, 4}.

Claim: A graph having a clean tree-decomposition is connected. Proof sketch: By using bottom-up induction of u in N T , one can prove that each graph G[T ≤ (u)] is connected. This fact holds because p T (w Proof: Let (T, f ) be a normal tree-decomposition of a connected graph G.

) ∈ f * T (w) for each w ∈ N T = V G , hence u is linked to G[T ≤ (w)] if u = p T (w).
We first compute f T in time O(|E G | . |N T |). Since G is connected, no set f * T (u)
is empty, except if u is the root (because then f T (u) = {u}). For each u ∈ N T such that p T (u) / ∈ f T (u), we let u be the least element of f * T (u) with respect to ≤ T . We modify T by making u the father of u, and we let T ′ be the new tree. Then (T ′ , f T ) is a clean tree-decomposition of G of same width as (T, f T ), that is no larger than that of (T, f).

If the sets f * T (u) are listed by increasing order with respect to ≤ T , then u is accessed in constant time, and so, we can construct T ′ in time O(|N T |).

Every connected graph has an optimal tree-decomposition that is clean. Clean tree-decompositions (used in [START_REF] Corneil | On the relationship between clique-width and tree-width[END_REF]) arise in a natural way from the notion of partial k-tree that we now recall. An undirected graph G is chordal if it is connected, its vertices can be denoted by 1, ..., n in such a way that G[N G (i)∩[i-1]] is a clique for each i = 2, ..., n (this is one definition among others, cf. [START_REF] Courcelle | Graph structure and monadic second-order logic, a language theoretic approach[END_REF], Proposition 2.72). A normal tree-decomposition (T, f T ) is obtained as follows: T has nodes 1, ..., n, root T := 1 and p T (i

) := min(N G (i) ∩ [i -1]). We have f * T (i) = N G (i) ∩ [i -1].
This tree-decomposition is optimal and clean. A partial k-tree is a graph obtained by edge deletions from a chordal graph G of maximal clique size k + 1. A graph H has tree-width at most k if and only if Und(H) is a partial k-tree. The tree-decomposition (T, f T ) of G is a normal tree-decomposition of H. If H is connected, this decomposition can be cleaned by the previous lemma.

Definition 6 : Special tree-decompositions. A tree-decomposition (T, f ) is special if any two nodes u, u ′ of T such that f(u) ∩ f(u ′ ) = ∅ are comparable with respect to ≤ T , equivalently, if f (u) ∩ f (u ′ )
= ∅ for any two distinct nodes u, u ′ with same father. We get the notion of special tree-width, denoted by sptwd. This notion has been introduced in [START_REF] Courcelle | On the model-checking of monadic second-order formulas with edge set quantifications[END_REF]. It is clear that twd(G) ≤ sptwd(G) but graphs of tree-width 2 have unbounded special tree-width. Graphs of special tree-width 2 have been studied in [START_REF] Bodlaender | Fixed-parameter tractability and characterizations of small special treewidth[END_REF][START_REF] Bouvier | Graphes et décompositions[END_REF].

Every special tree-decomposition can be made normal and special without increasing its width by the algorithm of Lemma 3. However, it cannot always be made clean and special : the star K 1,3 has a special tree-decomposition (actually a path-decomposition) of width 1 (sse Definition 4) but no clean and special tree-decomposition of this width. We will give a simple proof that cwd(G) ≤ sptwd(G) + 2 for every graph G, a result from [START_REF] Courcelle | On the model-checking of monadic second-order formulas with edge set quantifications[END_REF].

In the appendix, we will examine how quasi-normal tree-decompositions behave with respect to the minor quasi-order. We will not need the corresponding observations for our main results, but they prove that the notions of normal and quasi-normal tree-decomposition fit well to the theory of tree-width.

Clique-width

Clique-width is a graph complexity measure defined from operations that construct graphs equipped with vertex labels. We review definition and notation, and we establish a technical result.

= (V G , edg G , π G ) where π G is a mapping: V G → C. Its type is π(G) := π G (V G ),
i.e., the finite set of labels from C that label some vertex of G.

We denote by ≃ the isomorphism of C-graphs up to vertex labels, i.e., the isomorphism of the underlying unlabelled graphs.

A mapping h :

C → C is finite if h(a)
= a for finitely many labels a. It can be specified in a finitary way by listing the pairs (a, h(a)) such that h(a) = a. We denote by ∆(h) the set of these pairs.

We define F C as the following set of operations on C-graphs:

the union of two disjoint C-graphs, denoted by the binary function symbol ⊕, the unary operation relab h that changes every vertex label a into h(a) where h is a finite mapping from C to C, the unary operation --→ add a,b , for a, b ∈ C, a = b that adds an edge from each a-labelled vertex x to each b-labelled vertex y (unless there is already an edge x → y) and, for each a ∈ C, the nullary symbol a(x) that denotes the isolated vertex x labelled by a.

For building undirected graphs, we use similarly add a,b to add undirected edges. In a well-formed term t, no two occurrences of nullary symbols denote the same vertex 5 .

Every term t in T (F C ) is called a clique-width term. It denotes a C-graph G(t). We will denote π(G(t)) by π(t) and call it the type of t. The equivalence on terms t ≃ t ′ is defined as G(t) ≃ G(t ′ ) and t ≡ t ′ as G(t) = G(t ′ ) (vertices are specified in the terms t, t ′ ).

The clique-width of a graph G, denoted by cwd(G), is the least cardinality of a set

C such that G ≃ G(t) for some t ∈ T (F C ). It is frequently convenient to take C = [k].
As ⊕ is associative, we will use it as an operation of variable arity. For readability, we will write t = t 1 ⊕t 2 ⊕...⊕t n instead of ⊕(t 1 , t 2 , ..., t n ), defined as a shorthand for t 1 ⊕(t 2 ⊕(...⊕t n )...). We define the size |t| of t as |t 1 |+...+|t n |+n-1. If h only changes a into b, we denote relab h by relab a→b and call this operation an elementary relabelling. By using only elementary relabellings, we obtain the same notion of clique-width ( [START_REF] Courcelle | Graph structure and monadic second-order logic, a language theoretic approach[END_REF], Proposition 2.118). A relabelling relab h is bijective on a term t if h is injective on π(t), hence is a bijection : π(t) → h(π(t)). (See Section 6 about the use of these notions).

(b) Our proofs will use a characterization6 of clique-width allowing easy constructions of clique-width terms. If u ∈ P os(t), i.e., is a position in a term t ∈ T (F C ), then the subterm of t issued from u, denoted by t/u, denotes a C-graph G(t/u) that is, up to vertex labels, a subgraph of G(t) (because we use nullary symbols a(x) to designate vertices). Hence, G(t) = G(t/root T ). We define the width of t as wd(t)

:= max{|π(t/u)| | u ∈ P os(t)} ≤ |C| .
If k labels occur in a term t, then G(t) has clique-width at most k. However, k can be an overestimation of cwd(G(t)). The value of cwd(G(t)) that arises from t is actually wd(t) defined as the maximum number of labels that occur in a graph G(t/u) for any position u in t. This is proved in the next proposition.

Proposition 8 : The clique-width of a graph is the minimal width of a term that defines it, up to vertex labels and isomorphism. Every clique-width term t can be transformed into an ≃-equivalent term t ′ in T (F [wd(t)] ).

Proof: Let t ∈ T (F C ), G = G(t) and k = wd(t). First step. By replacing in t each subterm ⊕(t 1 , t 2 , ..., t n ) by t 1 ⊕ (t 2 ⊕ (... ⊕ t n )..))
, we get a ≡-equivalent term of same size as t where all occurrences of ⊕ are binary.

Second step. We fix t obtained by the first step and we denote π(t/u) by π(u).

We will compute in a bottom-up the following items, for each u ∈ P os(t) :

the set π(u),

the number k u := max{|π(w)| | w ≤ u} ≤ k, a injective mapping h u : π(u) → [k u ] such that t u ≡ relab hu (t/u).
The desired term t ′ will be t r where r is the first position of t (the root of its syntactic tree). The bottom-up computation uses the following clauses:

(1) If u is an occurrence of a(x), then π(u) = {a}, k u = 1 and h u maps a to 1.

(2) If t/u = --→ add a,b (t/w), then π(u) = π(w), k u = k w and we define h u := h w . If a or b is not in π(w), then the operation --→ add a,b has no effect and we define t u := t w . Otherwise, we define

t u := --→ add h w (a),h w (b) (t w ). (3) If t/u = relab h (t/w), then π(u) = h(π(w)), k u ≤ k w ; we take for h u any 7 injective mapping : π(u) → [k u ] and we define t u := relab h ′ (t w ) where h ′ := h u • h • h -1 w . (4) If t/u = t/w ⊕ t/w ′ , then π(u) = π(w) ∪ π(w ′ ), k u = |π(u)| ≥ k w , k w ′ and we take for h u any injective mapping : π(u) → [k u ]
whose restriction to π(w) is h w and we define t

u := t w ⊕ relab h (t w ′ ) where h := h u • h -1 w ′ .
The verification that t u ≡ relab hu (t/u) is straightforward by the same induction.

This proposition simplifies the constrution of clique-width terms because, in a first step, we can use infinite sets C of labels, and then, in a second step, we can use it to transform an obtained term in T (F C ), say t, into an ≃-equivalent term in T (F [wd(t)] ). However, we will see in Section 6 that fly-automata, as defined in [START_REF] Courcelle | Automata for the verification of monadic second-order graph properties[END_REF] can use terms of "small" width belonging to T (F C ) where C is "large".

One can also construct the terms t u in such a way that

π(t u ) = [|π(t u )|].
To do that we choose bijections 3) and ( 4)

h u : π(u) → [|π(t u )|] in Clauses (
(we recall that [|π(t u )|] ⊆ [k u ]
). This strengthening is not crucial for using fly-automata.

Some comparisons between tree-width and clique-width.

For every directed graph G, we have

twd(Und(G)) = twd(G) and cwd(Und(G)) ≤ cwd(G) ([12], Proposition 2.105(3)).
Theorem 9 : For all graphs G, the following hold:

(1) twd(G) is unbounded in terms of cwd(G), (2) cwd(G) ≤ 3 • 2 twd(G)-1 if G is undirected, (3) cwd(G) ≤ 2 2twd(G)+2 + 1 if G is directed. ( 4
) There is no constant a such that cwd(G) = O(twd(G) a ) for all graphs G.

Proof: Cliques have clique-width 2 and unbounded tree-width, which proves [START_REF] Arnborg | Complexity of finding embeddings in a k-tree[END_REF]. Assertions (2) and (3) are proved respectively in [START_REF] Corneil | On the relationship between clique-width and tree-width[END_REF] and in Proposition 2.114 of [START_REF] Courcelle | Graph structure and monadic second-order logic, a language theoretic approach[END_REF]. For each k, there exists an undirected graph of tree-width 2k and cliquewidth larger than 2 k-1 (a result from [START_REF] Corneil | On the relationship between clique-width and tree-width[END_REF]). This proves Assertion (4).

We will give a construction that proves easily (2) and improves the bound of (3). We recall that S r is the class of graphs G such that Und(G) does not contain a subgraph isomorphic to K r,r ; it contains the graphs of maximal degree at most r -1.

Theorem 10 : (1) If G has maximal degree at most d (with d ≥ 1), we have:

(1.1) twd(G) ≤ 3d • cwd(G) -1, (1.2) cwd(G) ≤ 20d(twd(G) + 1) + 2.
(2) If r ≥ 2 and G ∈ S r , we have twd(G) ≤ 3(r -1)cwd(G) -1.

Proof : Assertion (2) is from [START_REF] Gurski | The tree-width of clique-width bounded graphs without K n[END_REF] (also [START_REF] Courcelle | Graph structure and monadic second-order logic, a language theoretic approach[END_REF], Proposition 2.115) and it yields (1.1). Assertion (1.2) is proved in [START_REF] Courcelle | On the model-checking of monadic second-order formulas with edge set quantifications[END_REF] by means of a strong result of [START_REF] Wood | On tree-partition-width[END_REF].

Unlike the bounds of Theorem 9(2,3), that of Theorem 10(1.2) is the same for directed and undirected graphs. Theorem 10(2) shows that, for each q, twd(G) = O(cwd(G)) if G is uniformly q-sparse. An opposite (polynomial) bounding will be established in Theorem 19.

From tree-decompositions to clique-width terms

Most FPT algorithms parameterized by tree-width or clique-width take as input a tree-decomposition of the considered graph or a clique-width term defining it. Unfortunately, tree-width and clique-width (and the corresponding optimal decompositions and terms) are difficult to compute8 [START_REF] Arnborg | Complexity of finding embeddings in a k-tree[END_REF][START_REF] Fellows | Clique-width is NPcomplete[END_REF], but there exist polynomial time approximation algorithms.

There is a rich litterature on efficient algorithms that construct tree-decompositions [START_REF] Bodlaender | Treewidth computations I. Upper bounds[END_REF], but not so for clique-width. For many graphs, e.g. rectangular grids, clique-width and tree-width are equal, up to a small fixed constant. It is thus useful to transform tree-decompositions (or even quasi-normal trees) into cliquewidth terms. Theorem 9 is discouraging on first sight because of the exponential boundings, but for a number of useful graph classes (not only for graphs of bounded degree, cf. Theorem 10), we have cwd(G) = O(twd(G) q ), with even q = 1 for planar graphs and incidence graphs. We will give two algorithms that work for all types of graphs, and we will obtain such bounds from the first of them. The second one is more interesting for certain graphs of large clique-width.

Theorem 11: Let (T, f) be a quasi-normal tree-decomposition of a graph G. If |Ω(T < (u), f (u))| ≤ m for every node u of T , then cwd(G) ≤ m + 1. A clique-width term witnessing this bound can be constructed from (T, f ) in linear time.

Proof : The tree T is quasi-normal for G and V G ⊆ N T . We first consider G undirected. We will construct a term t ∈ T (F C ) that defines G, by using the set of labels C := { * } ⊎ P(V G ).

For each u ∈ N T , we define H(u) as the graph G[T ≤ (u)] where each vertex

w has label N G (w) ∩ T > (u) (in particular, u has label up G,T (u)). We have N G (w) ∩ T > (u) ⊆ f * T (u) ⊆ f * (u) and π(H(u)) = Ω(T ≤ (u), f * (u)). So, H(root T ) is G with all vertices labelled by ∅.
The following inductive characterization of H(u) yields immediately a term

t u in T (F C ) that denotes it. If u is a leaf, then H(u) = c(u), where c := up G,T (u) = N G (u).
Otherwise, u has sons u 1 , ..., u p . Then, if u / ∈ V G we have :

H(u) = H(u 1 ) ⊕ ... ⊕ H(u p ). (The label of a vertex w in H(u i ) is N G (w) ∩ T > (u i ) = N G (w) ∩ T > (u), hence is the same in H(u).)
If u ∈ V G we have :

H(u) = relab * →c (relab h (A( * (u) ⊕ H(u 1 ) ⊕ ... ⊕ H(u p ))))
where

c := up G,T (u),
A is the composition of the operations add * ,d such that The correctness is clear from the definition. We now bound the width of the terms t u . For doing that, we need to bound the cardinalities of the types of their subterms.

d ∈ π(H(u 1 ) ⊕ ... ⊕ H(u p )) and u ∈ d, h (
If

u is a leaf, then |π(H(u))| = |π(t u )| = 1 because t u = c(u). Otherwise, by the definitions, π(H(u)) = π(t u ) is the set of sets N G (w) ∩ T > (u) for w ≤ T u. As already noted, π(H(u)) = Ω(T ≤ (u), f * (u)).
We first consider the case where u ∈ V G . We have:

π(H(u i )) = Ω(T ≤ (u i ), f * (u i )) = Ω(T ≤ (u i ), f(u)) ⊆ Ω(T < (u), f (u)). (1)
Hence:

π(A( * (u) ⊕ H(u 1 ) ⊕ ... ⊕ H(u p ))) = π( * (u) ⊕ H(u 1 ) ⊕ ... ⊕ H(u p )) ⊆ { * } ∪ Ω(T < (u), f(u)), (2)
π(relab h (A( * (u) ⊕ H(u 1 ) ⊕ ... ⊕ H(u p )))) ⊆ { * } ∪ Ω(T < (u), f * (u)). (3)
We have also 9 :

π(H(u)) = {c} ∪ Ω(T < (u), f * (u)) = Ω(T ≤ (u), f * (u)). ( 4
)
If u / ∈ V G , the situation is simpler because π(H(u)) = π(H(u 1 )⊕ ... ⊕H(u p )) and π(H(u)) = Ω(T < (u), f(u)) = Ω(T ≤ (u), f (u)). ( 5
)
We now bound the cardinalities of these sets of labels. We have:

|Ω(T < (u), f * (u))| ≤ |Ω(T < (u), f(u))| ≤ m, hence |π(H(u))| ≤ m + 1
for each u, by ( 4) and [START_REF] Corneil | On the relationship between clique-width and tree-width[END_REF].

We also have :

|{ * } ∪ Ω(T < (u), f * (u))| ≤ 1 + |Ω(T < (u), f(u))| ≤ m + 1. (6)
Since, by induction, wd(t ui ) ≤ m + 1 for each i, we have wd(t u ) ≤ m + 1.

We now consider the case where G is directed. The proof is similar with

C := { * } ⊎ (P(V G ) × P(V G )). For each u ∈ N T , we define H(u) as the graph G[T ≤ (u)] where each vertex w has label (N + G (w) ∩ T > (u), N - G (w) ∩ T > (u)). Note that (N + G (w)∪N - G (w))∩T > (u) ⊆ f * (u). The inductive characterization of H(u) is as follows: If u is a leaf, then H(u) = c(u), where c := (up + G,T (u), up - G,T (u)).
Otherwise, u has sons u 1 , ..., u p . Then, if u / ∈ V G we have :

H(u) = H(u 1 ) ⊕ ... ⊕ H(u p ) and, if u ∈ V G : H(u) = relab * →c (relab h (A( * (u) ⊕ H(u 1 ) ⊕ ... ⊕ H(u p ))))
where The correctness is clear from the definition. We now bound the width of the terms t u . By the definitions, π(H(u)) = π(t u ) is the set of pairs (N + G (w) ∩ T > (u), N - G (w)∩T > (u)) for w ≤ T u and we also have

c := (up + G,T (u), up - G,T (u)), A is the composition of the operations --→ add (d,d ′ ), * such that (d, d ′ ) ∈ π(H(u 1 ) ⊕ ... ⊕ H(u p ))
(N + G (w)∪N - G (w))∩T > (u) ⊆ f(u) -{u} for each such w. Hence π(H(u)) = Ω(T ≤ (u), f * (u)). If u is a leaf, then |π(H(u))| = |π(t u )| = 1 as t u = c(u).
Otherwise u has sons u 1 , ..., u p and we have, similarly as (1):

π(H(u i )) = Ω(T ≤ (u i ), f * (u i )) = Ω(T ≤ (u i ), f(u)) ⊆ Ω(T < (u), f (u)).
Inqualities and equalities ( 2)-( 6) hold in the same way, and we have wd(t u ) ≤ m + 1.

Remarks : (1) Note that Ω(T ≤ (u), f * T (u)) = Ω(T ≤ (u), f * (u)) for all u. It follows that the construction is exactly the same if we replace f by f T ; we still have |Ω(T < (u), f T (u))| ≤ m for every node u. By Lemma 3, we can also transform (T, f) into a normal tree-decomposition.

(2) Let us examine the description of H(u) for u ∈ V G . If c := up G,T (u) / ∈ π(H(u 1 ) ⊕ ... ⊕ H(u p )), we have the simpler expression : (3) This construction does not use the full power of add a,b and --→ add a,b because these operations are applied (in the terms t u ) to graphs having only one vertex labelled by a or only one vertex labelled by b. Hence, we do not obtain optimal clique-width terms. For the graphs K n,n of clique-width 2, given by clean optimal tree-decompositions, we obtain clique-width terms of width 3. (Remark (2) does not apply.)

H(u) = relab h (A(c(u) ⊕ H(u 1 ) ⊕ ... ⊕ H(u p ))))
As an immediate consequence, we get that if G is undirected of tree-width k,

then cwd(G) ≤ 2 k+1 + 1 because then |f (u)| ≤ k + 1, so that |Ω(T < (u), f (u))| ≤ 2 k+1 for each u; if G is directed, then cwd(G) ≤ 2 2k+2 + 1. (If G is undi- rected, we have actually cwd(G) ≤ 2 k+1 because, if |f (u)| = k + 1, then f(u) /
∈ Ω(T < (u), f(u)). The second example below shows that the upper-bound 2 k+1 on the width of the constructed term can be reached.) However, we will obtain better bounds by means of Algorithm 12 below.

Examples : (1) If we apply this construction to the clique K n of tree-width n -1, by applying remark (2) above, we get an optimal clique-width term of width 2.

(

.))

where {d 1 , d 2 , ..., d p } = P -{∅} and d 1 = {1}. Then (T, f T ) is a normal treedecomposition of width k (It is optimal because the set of vertices [k +1] induces a clique). For u := k + 1, we have Ω(T < (u), f T (u)) = P and the other sets Ω(T < (u), f T (u)) are smaller. Hence, the constructed term has width |P | + 1 = 2 k+1 . However, it is not hard to construct a clique-width term for G of width k + 3. Hence, an optimal tree-decomposition does not produce necessarily an optimal clique-width term.

(3) The following example shows that different optimal tree-decompositions can yield clique-width terms of different width.

We let H be the undirected graph with vertex set [k] ⊎ Q where Q := {a 1 , ..., a k }. Its edges are ij for 1 ≤ i < j ≤ k, a ij for all 1 ≤ j < i. Let T be the normal tree 1(2(...(k(a 1 , a 2 , ..., a k )...)). Then (T, f T ) is a normal treedecomposition of width k that is optimal (because of the (k + 1)-clique induced by 1, ..., k, a k ) but not clean. For u := k, we have

Ω(T < (u), f T (u)) = {[1], ..., [k]} ([1], ..., [k]
are sets of vertices) and the other sets Ω(T < (u), f T (u)) are smaller. Hence, the constructed term has width k + 1.

The corresponding clean decomposition has tree T ′ = 1(a 1 , 2(a 2 , ...(k(a k )...)). We have Ω(T ′ < (i), f T ′ (i)) = {[i]} for each i, hence, we obtain a clique-width term of width 2, which is optimal.

That the tree-decomposition is clean is not enough to ensure that the constructed term has small width. Consider the tree T ′′ = k(...( 2(1(a 1 , a 2 , ..., a k )...)). The corresponding optimal tree-decomposition is clean but Ω(T

′′ < (k), f T ′′ (k)) = {[1], ..., [k]} and Ω(T ′′ < (i), f T ′′ (i)) = {∅, [1], ..., [i]} for each i = 1, ..., k -1.
We obtain a term of width k + 1.

Algorithm 12: Another construction of clique-width terms from tree-decompositions.

The input is a normal tree-decomposition (T, f) of a graph G such that

|Ω(T < (u), f(u))| ≤ m and |Ω(T < (u), f * (u))| ≤ m ′ for each u ∈ N T .
The output is a clique-width term denoting G of width at most m + m ′ + 1.

Method.

We first consider G undirected. As in Theorem 11, we construct a term t ∈ T (F C ) that denotes G where C := { * } ⊎ P(V G ). We use the same graphs H(u) but we construct them inductively in a different way.

If u is a leaf, then H(u) = c(u), where c := up G,T (u) = N G (u).
Otherwise, u (it is in V G ) has sons u 1 , ..., u p . Then, we define: Correctness is clear. This characterization yields a term t u that denotes H(u). We now bound the width of these terms t u , and for that, we examine the types of their subterms.

L 1 := relab h1 (A 1 (H(u 1 ) ⊕ * (u))), L i := relab hi (A i (H(u i ) ⊕ L i-1 )
We have π(H(u)) = Ω(T ≤ (u), f * (u)) for each u. In the above characterization: The largest of these sets are those of the form π(H(u i ) ⊕ L i-1 ). We have

π(L i ) = B i ∪ { * } for all i = 1, ..., p, where
B i := Ω(T ≤ (u 1 ), f * (u 1 ) -{u}) ∪ ... ∪ Ω(T ≤ (u i ), f * (u i ) -{u}), π(H(u i ) ⊕ L i-1 ) = Ω(T ≤ (u i ), f * (u i )) ∪ B i-1 ∪ { * }.
Ω(T ≤ (u i ), f * (u i )) ⊆ Ω(T < (u), f(u)) and B i-1 ⊆ Ω(T < (u), f * (u)), which gives |π(H(u i ) ⊕ L i-1 ))| ≤ m + m ′ + 1.
Hence, the terms t u have width at most m + m ′ + 1.

For directed graphs, the proof is the same by modifying the operations A i , similarly as we did in the second part of the proof of Theorem 11 .

Example : Let G be the graph of tree-width 3 of Figure 2 and let T = a(b(c(d, e, g, h, i))) (cf. Example 2 for the linear notation of trees). Then (T, f T ) is a clean and optimal tree-decomposition of G. The construction of Theorem 11 yields a clique-width term of width 5 because Ω(T < (c), f T (c) = {{c}, {a, c}, {b, c}, {a, b, c}} and the other similar sets are strictly smaller.

Let us now use Algorithm 12. For u := c, we let (u 1 , ..., u 5 ) := (d, e, g, h, i). Then π(H(u 5 ) ⊕ L 4 ) = {{c}} ∪ {∅, {a}, {b}, {a, b}} ∪ { * } of cardinality 6. The other similar sets are strictly smaller and the constructed term has width 6.

The construction of Algorithm 12 looks less interesting than that of Theorem 11, but it gives better bounds on the clique-width in certain cases.

Proposition 13 : From a clean tree-decomposition of width k, Algorithm 12 produces a clique-width term of width at most 3.2 k-1 if the graph is undirected and at most 7.2 2(k-1) if it is directed.

Proof: We examine carefully the types of the subterms of t u as in the proof of Theorem 11. The only case to consider is that of u ∈ V G with sons u 1 , ..., u p . Since the given tree-decomposition (T, f) is clean, u ∈ f(u i ) for each i. Furthermore, if |f(u)| = k+1, then f(u)-{u} contains, for each i, at least one

vertex not in f (u i ) (because otherwise, f (u i ) = f (u)∪ {u i } and |f (u i )| = k + 2).
We denote by u i such a vertex.

Consider now :

π(H(u i ) ⊕ L i-1 ) = Ω(T ≤ (u i ), f * (u i )) ∪ B i-1 ∪ { * }.
We assume first that |f (u)| = k + 1.We have :

B i-1 = 1≤j≤i-1 Ω(T ≤ (u j ), f * (u j ) -{u}) ⊆ Ω(T < (u), f * (u)) but f * (u) / ∈ Ω(T < (u), f * (u)
) because of the vertices u 1 , ..., u p . Hence :

π(H(u i ) ⊕ L i-1 ) ⊆ Ω(T ≤ (u i ), f * (u i )) ∪ { * } ∪ P(f * (u)) -{f * (u)}.
The sets in Ω(T

≤ (u i ), f * (u i )) cannot contain u i , hence f * (u) / ∈ Ω(T ≤ (u i ), f * (u i )).
The sets in Ω(T ≤ (u i ), f * (u i )) that are not in P(f * (u)) -{f * (u)} must contain u, hence, are of the form {u} ∪ d for d ∈ P(f * (u) -{ u i }) and so, there are at most 2 k-1 such sets. As |P(f * (u)) -{f * (u)}| = 2 k -1, we have :

|π(H(u i ) ⊕ L i-1 )| ≤ 2 k-1 + 2 k -1 + 1. If |f (u)| ≤ k, then B i-1 ⊆ P(f * (u)) and so, |B i-1 | ≤ 2 k-1 . The sets in Ω(T ≤ (u i ), f * (u i )) that are not in P(f * (u)) must contain u, hence, there are at most 2 k-1 such sets. We obtain |π(H(u i ) ⊕ L i-1 )| ≤ 2 k-1 +2 k-1 +1 < 2 k-1 +2 k .
Hence, all terms t u have width bounded by 2 k-1 + 2 k = 3.2 k-1 . (This bound is due to [START_REF] Corneil | On the relationship between clique-width and tree-width[END_REF] where a similar construction is sketched).

We now consider the case where G is directed. We have similar inclusions. If |f (u)| = k + 1, we have :

B i-1 ⊆ Ω(T < (u), f * (u)) ⊆ P where P is P(f * (u)) 2 -{(f * (u), d), (d, f * (u)) | d ⊆ f * (u)}. Hence, |B i-1 | ≤ (2 k -1) 2 .The pairs (d, d ′ ) in Ω(T ≤ (u i ), f * (u i )) -P must contain u in d ∪ d ′ .
The number of such pairs is bounded by 3.2 2(k-1) (because there are 2 k-1 sets included in f * (u) -{u i }). We obtain thus the bound 2 and the number of pairs in

3.2 2(k-1) + (2 2k -2.2 k + 1) + 1 = 7.2 2(k-1) -2 k+1 + 2 < 7.2 2(k-1) . If |f (u)| = k, we have |B i-1 | ≤ (2 k-1 )
Ω(T ≤ (u i ), f * (u i )) -(P(f * (u)) × P(f * (u)))
is bounded again by 3.2 2(k-1) . We obtain thus the bound

3.2 2(k-1) + 2 2(k-1) ) + 1 < 7.2 2(k-1)
which completes the proof.

For sake of completeness, we give a third construction from [START_REF] Courcelle | On the model-checking of monadic second-order formulas with edge set quantifications[END_REF] that applies only to special tree-decompositions (cf. Definition 6). Its description is easier than that of that article.

Proposition 14 : If a graph G has special tree-width k, then cwd(G) ≤ k+2. A clique-width term witnessing this bound can be constructed in linear time from a special tree-decomposition of width k.

Proof: Let (T, f) be a special tree-decomposition of a graph G. We can assume it is normal and V G = N T . The proof is the same for directed and undirected graphs. We will use the set of labels C := {⊥} ⊎ V G . For each u ∈ N T , we define K(u) := G[T ≤ (u) ∪ f(u)] and we label its vertices as follows :

π(w) := if N G (w) ⊆ T ≤ (u) then ⊥ else w.
If π(w) = ⊥ then w ∈ f(u). These graphs satisfy the follows inductive characterization :

If u is a leaf, then

K(u) = G[f (u)] with the labelling π. It can be defined by a term t u of width |f (u)| ≤ k + 1.
Otherwise, u has sons u 1 , ..., u p , and the sets T ≤ (u i )∪f (u i ) are pairwise disjoint because (T, f) is special. We let {v 1 , ..., v q } := f(u)-(f(u 1 )∪...∪f(u p )), q ≥ 0; these vertices are not in K(u 1 ) ⊕ ... ⊕ K(u p ). We have :

K(u) = relab h (A(K(u 1 ) ⊕ ... ⊕ K(u p ) ⊕ v 1 (v 1 ) ⊕ ... ⊕ v q (v q ))),
where :

A is a composition of the edge additions that create the edges of K(u) not in K(u 1 ) ⊕ ... ⊕ K(u p ), and h maps v to ⊥ for all v = ⊥ such that π(v) = ⊥ (in K(u)).

We now bound the width of t u in these last two cases.

π(K(u)) ⊆ f (u) ∪ {⊥}, π(K(u 1 ) ⊕ ... ⊕ K(u p ) ⊕ v 1 (v 1 ) ⊕ ... ⊕ v q (v q )) ⊆ f (u) ∪ {⊥}. Hence, cwd(G) ≤ k + 1 + 1 = k + 2.
Remark 15 : (1) As in Theorem 11 and Algorithm 12, we do not use the full power of the edge addition operations. The operations in A create edges with both ends in the set f(u) that has cardinality at most k + 1.

(2) If the given decomposition (T, f ) is not special, we can denote G by a term built with the operation of parallel composition: for edge disjoint graphs H and

K (i.e., E H ∪ E K = ∅), H//K := (V H ∪ V K , E H ⊎ E K ).
The graphs G[f(u)] (without vertex labels) are defined inductively similarly as above. If u has sons u 1 , ..., u p , then:

G[f(u)] = G[f (u 1 )]//...//G[f (u p )]//A u
where A u consists of the edges and vertices of

G[f (u)] not in G[f(u 1 )]//...// G[f (u p )].
In a subsequent step, similar to the algorithm of Proposition 8, we can allocate "source" labels in [k + 1] to convert the term that defines G[f (u)] into a term of the "HR graph algebra" of [START_REF] Courcelle | Graph structure and monadic second-order logic, a language theoretic approach[END_REF], Chapter 2.

Sparse graphs

We apply Theorem 11 to several classes of sparse graphs. We first consider the class P of (simple) planar graphs. They are uniformly 3-sparse.

Planar graphs

Smoothing a vertex of degree 2 that has neighbours y and z in an undirected graph means replacing it and its two incident edges by a single edge between y and z, and then, fusing the parallel edges that may result. This transformation preserves planarity.

Lemma 16 : Let k ≥ 3, G ∈ P, X, Y ⊆ V G be such that X ⊆ Y c and |Y | ≤ k. 1) If G is undirected, then |Ω(X, Y )| ≤ 6k -9. 2) If G is directed, then |Ω(X, Y )| ≤ 32k -57.
If k ≤ 2, the upper bounds are respectively 4 and 13.

Proof: 1) This assertion is Proposition 11 of [START_REF] Fomin | Rank-width and tree-width of H-minorfree graphs[END_REF]. We prove it for completeness and in order to prove the corresponding assertion about directed graphs. We consider disjoint sets X and Y, with Y of cardinality k, and we bound the number |Ω(X, Y )|, i.e. the number of sets of the form N G (x) ∩ Y for some x ∈ X.

We will bound |Ω(X, Y )| for graphs having edges between X and Y only. This suffices because removing the other edges and the vertices in X c -Y preserves planarity and does not modify Ω(X, Y ).

We denote by X 1 , X 2 and X 3 the sets of vertices of X having degree, respectively, at most 1, exactly 2 and at least 3. We have

|Ω(X 1 , Y )| ≤ k + 1.
Next we consider the vertices in X 2 . We remove from G the vertices in X -X 2 . We obtain a planar graph G ′ . By smoothing its vertices from X 2 , we get a graph

H ∈ P with vertex set Y of cardinality k. Each edge of H corresponds to a set in Ω(X 2 , Y ). Hence, |Ω(X 2 , Y )| = |E H | ≤ 3k -6.
We now consider the vertices in X 3 . We remove from G the vertices in X -X 3 . We get a bipartite graph K ∈ P with edges between V K = X 3 and Y . As each vertex in X 3 has degree at least 3 in K, we have 3

|X 3 | ≤ |E K | . As K is planar and bipartite, |E K | ≤ 2 |V K | -4. Hence, 3 |X 3 | ≤ |E K | ≤ 2(|X 3 | + k) -4 which gives |X 3 | ≤ 2k -4, and so, |Ω(X 3 , Y )| ≤ |X 3 | ≤ 2k -4. Hence, |Ω(X, Y )| = |Ω(X 1 , Y )|+|Ω(X 2 , Y )|+|Ω(X 3 , Y )| ≤ k+1+3k-6+2k-4 = 6k-9.
2) Assume now that G is directed. The undirected graph Und(G) is obtained from G by forgeting edge directions and fusing any two parallel edges. We define X 1 , X 2 and X 3 as above with degrees evaluated in Und(G). Each edge between u and v in Und(G) can come from three types of edges in G: u → v, v → u and two opposite edges between u and v. Hence, |Ω(X 1 , Y )| ≤ 3k + 1. By this observation, |Ω(X 2 , Y )| is at most 9 times the corresponding value in Und(G), hence |Ω(X 2 , Y )| ≤ 9(3k -6). The above proof for an undirected graph shows that 2k -

4 bounds |X 3 | hence Ω(X 3 , Y ). Hence, we get |Ω(X, Y )| ≤ 3k + 1 + 9(3k -6) + 2k -4 = 32k -57.
The bounds 3k -6 (resp. 2k -4) on numbers of edges of simple planar graphs (resp. simple planar bipartite graphs) are valid if k ≥ 3. Otherwise, inspecting the proofs yields the bounds 1 + 2 + 1 = 4 for undirected graphs and 1 + 3 + 9 = 13 for directed graphs.

Theorem 17: The clique-width of a simple planar graph of tree-width k ≥ 2 is at most 32k -24 if it is directed, and at most 6k -2 if it is undirected.

Proof: We apply Lemma 16 and Theorem 11, by noting that each set f (u) has at most k + 1 elements. We get the bounds 32(k + 1) -57 + 1 = 32k -24 on the clique-width of a directed graph and 6(k + 1) -9 + 1 = 6k -2 for an undirected one.

It follows from this result and Theorem 10(2) (a result from [START_REF] Gurski | The tree-width of clique-width bounded graphs without K n[END_REF]) that cliquewidth and tree-width are linearly related.

Related work. By using the fact that the rank-width of an undirected graph is at most its tree-width plus 1 (proved in [START_REF] Oum | Rank-width is less than or equal to branch-width[END_REF]), the article [START_REF] Fomin | Rank-width and tree-width of H-minorfree graphs[END_REF] establishes that the clique-width of a planar undirected graph is bounded by 12twd(G) + 11.

It proves also that, if G, undirected, is embeddable in a surface of Euler genus r (i.e., a sphere with h handles and r -2h crosscaps) the bounds 3k -6 and 2k -4 in the proof of Lemma 16(1) are replaced by 3k -6 + 3r and 2k -4 + 2r respectively. The corresponding modifications of Lemma 16 [START_REF] Bodlaender | Treewidth computations I. Upper bounds[END_REF] and Theorem 17 give the bounds cwd(G) ≤ 32twd(G) + O(r) for G directed and cwd(G) ≤ 6twd(G) + O(r) for G undirected, where in both cases, G is embedded on some surface of genus r.

Uniformly q-sparse graphs

We recall from Section 1 that γ(k, q) denotes the number of subsets of [k] of cardinality at most q. It is O(k q ) for fixed q and bounded by k q /(q -1)! if 1 < q < k/2. We will use γ(k, q) for "small", fixed values of q.

Lemma 18 : Let k ≥ q > 1 and G be uniformly q

-sparse. Let X, Y ⊆ V G be such that X ⊆ Y c and |Y | ≤ k. 1) If G is undirected, then |Ω(X, Y )| ≤ qk + γ(k, q). 2) If G is directed, then |Ω(X, Y )| ≤ qk + 3 q γ(k, q).
Proof: Let k ≥ q > 1 and G be uniformly q-sparse. We let X and Y be as in the proof of Lemma 16 and we bound |Ω(X, Y )| .

1) Let G be undirected and H be an orientation of G of indegree at most q (cf. Section 1). As in the proof of Lemma 16, we can assume that G and H are bipartite with edges between X and Y .

Let X 1 be the set of vertices x ∈ X such that N + H (x) is not empty. Since the orientation has indegree at most m and

N + H (x) ⊆ Y, |X 1 | ≤ qk and hence, |Ω(X 1 , Y )| ≤ |X 1 | ≤ qk. (Ω is relative to G). For each vertex x of X 2 := X -X 1 , we have N + H (x) = ∅ and N - H (x)
is a subset of Y of cardinality at most q. There are at most γ(k, q) such sets, hence, |Ω(X 2 , Y )| ≤ γ(k, q). We get the claimed upper-bound since

|Ω(X, Y )| ≤ |Ω(X 1 , Y )| + |Ω(X 2 , Y )| .
2) We apply this argument to Und(G) that is uniformly q-sparse. We still have |Ω(X 1 , Y )| ≤ qk but |Ω(X 2 , Y )| ≤ 3 q γ(k, q) as each edge of H can arise from three configurations of edges in G.

Theorem 19 : For each q ≥ 1, if G is uniformly q-sparse, then cwd(G) = O(twd(G) q ).
Proof: Immediate consequence of Lemma 18 and Theorem 11.

We get cwd(G) = O(twd(G) ⌈d/2⌉ ) for graphs of degree at most d (where the constant depends on d), but Theorem 10(1.2) gives a better, linear upper-bound. Since planar graphs are uniformly 3-sparse, we get cwd(G) = O(twd(G) 3 ) for them, but Theorem 17 also gives linear upper-bounds. Related work. Theorem 21 of [START_REF] Fomin | Rank-width and tree-width of H-minorfree graphs[END_REF] proves that for every (fixed) r, we have cwd(G) = O(γ(twd(G), r)) = O(twd(G) r ) for every undirected graph G in S r (the class of graphs G with no subgraph of U nd(G) isomorphic to K r,r ). As every uniformly m-sparse undirected graph G belongs to S 2m+1 , we deduce that cwd(G) = O(twd(G) 2m+1 ) (for fixed m) but the bound of Theorem 19 is better.

Bipartite graphs and hypergraphs

Bipartite gaphs are interesting for many reasons. In particular, they can encode incidence graphs and hypergraphs as we will see, and also satisfiability problems for propositional formulas [START_REF] Fischer | Counting truth assignments of formulas of bounded tree-width or clique-width[END_REF].

A bipartite graph G is d-bounded if all vertices of one of the two parts of V G have degree at most d. For such a graph, Und(G) has an orientation of indegree at most d, hence Theorem 19 gives cwd(G) = O(twd(G) d ). We will improve this bound.

Hypergraphs as bipartite graphs

Definition 20: Hypergraphs and their tree-decompositions.

(a) A hypergraph is a triple H = (V H , E H , inc H ) such that V H and E H are disjoint nonempty sets and inc H ⊆ V H × E H ; V H is the set of vertices, E H is the set of hyperedges and (v, e) ∈ inc H means that v is a vertex of e (we also say that e is incident to v). In order to avoid uninteresting technical details, we assume that each hyperedge has at least one vertex and that each vertex belongs to some hyperedge. A hypergraph is a q-hypergraph if its hyperedges have at most q vertices. The directed bipartite graph associated with H is Bip(H) := (V H ∪ E H , inc H ) and H can be reconstructed from Bip(H). If H is a q-hypergraph, then Bip(H) is q-bounded. We also define the undirected graph K(H) with set of vertices V H and edges between any two vertices belonging to some hyperedge.

(b) A tree-decomposition of a hypergraph H is a pair (T, f) as for graphs with the condition that each hyperedge must have all its vertices in some set f(u). Equivalently, (T, f) is a tree-decomposition of K(H) because, for any treedecomposition (T ′ , g) of a graph, each clique of this graph is contained in some set g(u). The width of (T, f) and the tree-width twd(H) of H together with the notions of normal, clean and quasi-normal tree-decompositions are as for K(H).

Figure 3 shows the graph G = Bip(H) associated with a 3-hypergraph H with hyperedges t, u, v, w, x, y, z and the tree T of a tree-decomposition (T, f ) of H of width 2; the function f is defined in the following table (s ∈ N T ). In the figure, hyperedges are circled, and the edges of Bip(H) are undirected. (2) If H is a q-hypergraph, then twd(H) ≤ q(twd(Bip(H)) + 1) -1.

Proof sketch : (1) Let (T, f ) be a tree-decomposition of H. For each hyperedge e, there is a node u of T such that all vertices of e are in f (u) and we add to T a new son u ′ of u with associated set {e} ∪ f(u). We get a tree-decomposition of Bip(H) of width twd(Bip(H)) + 1.

(2) Let (T, f ) be a tree-decomposition of Bip(H) of width k such that H is a q-hypergraph. We define f ′ (u) :=

f (u) ∪ {x ∈ V H | inc H (x, e) for some e ∈ f(u) ∩ E H } -(f (u) ∩ E H ).
Then (T, f ′ ) is a tree-decomposition of H and |f ′ (u)| ≤ q |f(u)| ≤ q(k + 1) which yields the result. (This result is a remark after Theorem 5.4 in [START_REF] Kolaitis | Conjunctive-query containment and constraint satisfaction[END_REF]). This lemma shows that for fixed q, the tree-width of a q-hypergraph and that of its associated bipartite graph are linearly related. Theorem 19 shows that cwd(Bip(H)) = O(twd(Bip(H)) q ) for a q-hypergraph. We have cwd(Bip(H)) = O(twd(H) q ) by this fact and Lemma 21 but we can do better.

Theorem 22: Let q ≥ 2. For every q-hypergraph H, we have: cwd(Bip(H)) ≤ γ(twd(H) + 1, q -1) + 1 = O(twd(H) q-1 ).

Proof: Let (T, f T ) be a normal tree-decomposition 10 of H, i.e. of K(H), of width k = twd(H). The vertices of a hyperedge e are in f T (u) for some node u of T , hence are linearly ordered by ≤ T because (T, f T ) is normal; we let e be the smallest one.

We extend T into a tree U with set of nodes N T ∪ E H as follows. For each u ∈ V H , we let e 1 , ..., e m be the hyperedges e such that e = u; we replace the edge up T (u) of T by the path ue 1 -...e mp T (u); if m = 0 we do nothing; if u is the root, we put the path e 1 -...e m above u with e m as new root (these hyperedges have u as unique vertex). The vertices of a hyperedge e are e that is below it (in U ), and, at most q -1 vertices that are above. It is clear that U is a normal tree for Bip(H). We obtain a normal treedecomposition (U, f U ) of Bip(H). (It is not the tree-decomposition constructed in the proof of Lemma 21(1); its width is not bounded in terms of k: just consider several parallel edges between two vertices.) In order to use Theorem 11, we bound the cardinalities of the sets Ω(U < (w), f U (w)).

If w ∈ V H , then Ω(U < (w), f U (w)) consists of the following sets:

first, the sets N Bip(H) (u) ∩ f U (w) for u ∈ V H , u < U w; these sets are empty, because the neighbours in Bip(H) of such u are hyperedges e such that e < T u or e = u but, in both cases, e < T w, hence e / ∈ f U (w);

second, the sets N Bip(H) (e) ∩ f U (w) for e ∈ E H , e < U w; these sets are subsets of f T (w) of cardinality at most q-1, because they are the sets of ends v ≥ T w of the edges of K(H) whose other end is e < U e;

(in the example of Figure 4, for w := c, the sets in Ω(U < (w), f U (w)) are ∅, {c} and {a, c}).

Hence, |Ω(U < (w), f U (w))| ≤ γ(k + 1, q -1).

If w = e ∈ E H , then Ω(U < (w), f U (w)) consists of the following sets: second, the sets N Bip(H) (e 1 ) ∩ f U (e) for e 1 ∈ E H , e 1 < U e: these sets are subsets of f * T ( e) of cardinality at most q -1, because they are the sets of ends v ≥ e > e of the edges of K(H) whose other end is below e, hence below e or equal to it; (in the example of Figure 4, we have

N Bip(H) (w O ) ∩ f U (x O ) = {a, c}). Hence, |Ω(U < (w), f U (w))| ≤ 1 + γ(k, q -1) ≤ γ(k + 1, q -1)
. The claimed result 11 follows then from Theorem 11.

Incidence graphs

Let G be undirected, possibly with loops and parallel edges. Its incidence graph The following corollary of Theorem 22 is proved in [START_REF] Bouvier | Graphes et décompositions[END_REF] in a different way.

Inc(G) is the bipartite graph (V G ∪ E G , inc G ) such that inc G := {(v, e) ∈ V G ×E G | v is a vertex of e}. A loop has degree one in Inc(G). If G is considered as a 2-hypergraph, then Inc(G) = Bip(G). If G is directed, then Inc(G) is defined as (V G ∪ E G , inc G ) with inc G := {(v, e) ∈ V G × E G | e : v → G w for some vertex w} ∪ {(e, v) ∈ E G × V G | e : w → G v
Corollary 23 : We have cwd(Inc(G)) ≤ twd(G) + 3 if G is undirected and cwd(Inc(G)) ≤ 2twd(G) + 4 if it is directed. Proof : If G is undirected, Theorem 22 yields that the clique-width of Inc(G) = Bip(G) is bounded by γ(twd(G) + 1, 1) + 1 = twd(G) + 3.
If G is directed, we construct U as in the proof of Theorem 22. In that case, every edge e of G that is not a loop links a vertex e below it in U and one above it. If it is a loop, then e → e and e → e. We use the notation of the proof of Theorem 11 for directed graphs. The sets Ω(U < (w), f U (w)) consist of the pairs

(N + Inc(G) (u) ∩ f U (w), N - Inc(G) (u) ∩ f U (w)) for u < U w. If w ∈ V G , Ω(U < (w), f U (w)) consists of (∅, ∅) and pairs (v, ∅) or (∅, v) for some v ∈ f U (w). Hence, |Ω(U < (w), f U (w))| ≤ 1 + 2(k + 1). If w = e ∈ E G , then Ω(U < (w), f U (w)) consists of (∅, ∅), the pair (N + Inc(G) ( e)∩ f U (e), N - Inc(G) ( e) ∩ f U (e)
) and pairs (v, ∅) or (∅, v) for some v ∈ f T ( e) -{ e}. Hence, |Ω(U < (w), f U (w))| ≤ 1 + 1 + 2k < 2k + 3. We obtain the bound 2k + 4 by Theorem 11.

Remark 24 : The empty set (or the pair (∅, ∅)) is used in the construction of a term that denotes Inc(G) as a label for its vertices in V G as well as in E G . In view of application to the model-checking of MSO 2 properties (see Section 6 and [START_REF] Courcelle | Fly-automata for checking monadic second-order properties of graphs of bounded tree-width[END_REF][START_REF] Courcelle | Fly-automata for checking MSO 2 graph properties[END_REF]), it is useful to distinguish labels for vertices in V G from those for vertices in E G . In that case, we duplicate these "empty" labels (and no others). So, we can construct Inc(G) with two labels for the vertices of G and twd(G)+ 2 labels for its edges, i.e., the vertices in E G ⊆ V Inc(G) . If G is directed these figures are respectively 2 and 2twd(G) + 3.

Algorithmic applications

We discuss some applications of our constructions to the verification of monadic second-order expressible graph properties (MSO properties in short) by means of automata that process clique-width terms denoting the input graphs. This method is implemented in the running system AUTOGRAPH 13 . This section being informal, we will use examples and we refer the reader to [START_REF] Courcelle | Graph structure and monadic second-order logic, a language theoretic approach[END_REF][START_REF] Courcelle | Automata for the verification of monadic second-order graph properties[END_REF] for definitions.

Model-checking with fly-automata

We give the example of a monadic second-order (MSO) sentence 14 expressing that a graph G, defined as the relational structure V G , edg G , is 3-colorable. This sentence is ∃X, Y.Col(X, Y ) where Col(X, Y ) is the formula

X ∩ Y = ∅ ∧ ∀u, v.{edg(u, v) =⇒ [¬(u ∈ X ∧ v ∈ X) ∧ ¬(u ∈ Y ∧ v ∈ Y )∧ ¬(u / ∈ X ∪ Y ∧ v / ∈ X ∪ Y )]},
expressing that X, Y and V G -(X ∪Y ) are the three color classes of a proper 3-coloring of the considered graph G.

An MSO sentence intended to express a graph property can only use quantifications over vertices and sets of vertices. More powerful are the MSO 2 sentences, that can also use quantifications over edges and sets of edges. We recall the following "algorithmic meta-theorem" [START_REF] Courcelle | Graph structure and monadic second-order logic, a language theoretic approach[END_REF][START_REF] Courcelle | Linear-time solvable optimization problems on graphs of bounded clique-width[END_REF][START_REF] Downey | Parameterized complexity[END_REF][START_REF] Downey | Fundamentals of parameterized complexity[END_REF].

Theorem 25 : (a) For every integer k and every MSO sentence ϕ, there exists a linear-time algorithm that checks the validity of ϕ in any graph given by a term in T (F [k] ), whence of clique-width at most k. The computation time is linear in the size of the term.

(b) For every integer k and every MSO 2 sentence ϕ, there exists a lineartime algorithm that checks the validity of ϕ in any graph given by a treedecomposition of width k, whence of tree-width at most k. The computation time is linear in the size of the tree-decomposition. Assertion (b) 15 is actually a consequence of (a) because :

(1) an MSO 2 property of a graph G is nothing but an MSO property of its incidence graph Inc(G),

(2) if G has tree-width k, then Inc(G) has clique-width at most f (k) for some fixed linear function f (cf. Corollary 23), and

(3) a tree-decomposition of G of width k can be converted in linear time (for fixed k) into a clique-width term of width at most f (k) that defines Inc(G).

Point ( 1) is just a matter of definitions. Point (2) and the linear-time transformation of (3) make practically usable this reduction of (b) to (a). This fact is developped in [START_REF] Courcelle | Fly-automata for checking monadic second-order properties of graphs of bounded tree-width[END_REF][START_REF] Courcelle | Fly-automata for checking MSO 2 graph properties[END_REF]. MSO 2 sentences are more expressive than MSO ones, but bounded tree-width is necessary for having FPT algorithms to check the corresponding properties in this way, via incidence graphs. Some linear-time algorithms intending to implement (a) use finite automata that take as input terms t in T (F [k] ) and answer whether the graph G(t) satisfies the considered property. However, these automata are much too large to implementable in the classical way by means of transition tables. To the opposite, fly-automata (FA in short) compute the transitions that are needed during the run on a given term and thus overcome the size obstacle.

We review FA informally. Let C be a countably infinite set of labels. A deterministic fly-automata A over F C has a possibly infinite set of states Q A ⊆ (C ⊎ B) * where B is a finite set of auxiliary symbols, typically T rue, 0, 1, (, ), {, },", " etc. Its transitions are of the forms a → A p, f [q] → A p and ⊕[q, q ′ ] → A p, where a ∈ C, f ∈ F C is unary, q, q ′ , p ∈ Q A and p is defined in a unique way by an algorithm (that is part of the definition of A) from a, or from f and q, or from q and q ′ . The (possibly infinite) set Acc A ⊆ Q A of accepting states is decided by an algorithm. It follows that, on each term t, the automaton A has a unique (bottom-up) run. This run is computable and so is q A (t), the deterministic FA A(ϕ) over F C that recognizes the language L(ϕ). However, in Example 26, we have constructed an FA "directly" from our understanding of 3-colorability, without using its expression by an MSO sentence.

Let h : C → C ′ be a bijection. It extends into a bijection F C → F C ′ (each label a ∈ C occurring in a symbol of F C is replaced by h(a)) and into a bijection T (F C ) → T (F C ′ ); both are denoted by h. The deterministic FA h(A(ϕ)) over F C ′ , obtained from A(ϕ) by replacing f by h(f ) and each state q by h(q) in each transition, is the one constructed by MC where we replace C by C ′ . We have L(h(A(ϕ))) = h(L(A(ϕ))).

Theorem 27 : Let C be a countable set of vertex labels. There is an algorithm that constructs, for each MSO sentence ϕ, a deterministic FA A(ϕ) over F C that recognizes the language L(ϕ) ⊆ T (F C ) and satisfies the following properties, for all t, t ′ ∈ T (F C ):

(i) q A(ϕ) (t) ∈ (B ⊎ π(t)) * where B is a finite set disjoint from C, (ii) if G(t) is isomorphic to G(t ′ ), then q A(ϕ) (t) = q A(ϕ) (t ′ ), (iii) if h : C → C ′ is a bijection and B ∩C ′ = ∅, then q h(A(ϕ)) (h(t)) = h(q A(ϕ) (t)).

The proof is by induction on the structure of ϕ (an adequate inductive assertion is used for formulas with free variables). See [START_REF] Courcelle | Automata for the verification of monadic second-order graph properties[END_REF][START_REF] Courcelle | Fly-automata, model-checking and recognizability[END_REF]. It follows from (iii) that a set of labels C can be replaced by C ′ in bijection with C by h: the computation of h(A(ϕ)) over h(t) is the same as that of A(ϕ) over t, up to the replacement in the run of each label a by h(a). However, a difference in the computation times of h(A(ϕ)) and A(ϕ) may arise from the codings of labels. The computation time τ A(ϕ) (u) of a transition is bounded by a ϕ .θ.τ ′ A(ϕ) (u) where τ ′ A(ϕ) (u) is the number of comparisons of two labels during the computation of the state at a position u in terms of the states at its sons θ bounds the time taken for one comparison and a ϕ depends only on ϕ. If t ∈ T (F [k] ) where k is "small", then, one can take θ = 1. This may not be the same if C is "large", as in Theorem 11 and Algorithm 12. Hence, although FA can take as inputs terms in T (F C ) for large sets C, this observation motivates the use of Proposition 8.

However, the algorithm of Proposition 8 does not build a bijection h from C to N + making t ∈ T (F C ) into an equivalent term h(t) in T (F [cwd(t)] ). For each t ∈ T (F C ) and each position u of t, it defines a term t u , and a bijection h u : π(t/u) → π(t u ) ⊆ N + such that t u ≡ relab h u (t/u). It follows from Assertions (ii) and (iii) of Theorem 27 that q A ′ (ϕ) (t u ) = h u (q A(ϕ) (t/u)) for each u ∈ P os(t), where A ′ (ϕ) is the FA over T (F N + ) constructed from ϕ by algorithm MC. The term t u is, in most cases, larger than t/u because it is built from it by insertions of relabellings. However, these relabellings are bijective (see the next section) and the corresponding transitions are nothing but substitutions of symbols in the words that represent the states.

Hence, to conclude, a sentence of ϕ can be checked by running A(ϕ) either on a term t over F C , where C may be much larger than its width, or on an We first replace (T, f ) by (T, f T ) that is quasi-normal and of no larger width. The tree T is quasi-normal for H. Let f ′ T be the corresponding "minimal" mapping (cf. Definition 1(c)), so that (T, f ′ T ) is a quasi-normal tree-decomposition of H. We examine its width.

The only vertices w for which f ′ T (w) might differ from f T (w) are those that are comparable with v with respect to ≤ T . We consider the different cases:

Case 1 : w < T v. If v ∈ f T (w), then f ′ T (w) = (f T (w) -{v}) ∪ {u}, otherwise f ′ T (w) = f T (w).

Case 2 : w = v. Then f ′ T (w) = f ′ T (v) ⊆ f * T (v). Case 3 : v < T w < T u. We have u ∈ f T (w) (because of the contracted edge or edges); it follows that f ′ T (w) = f T (w) because the only redirected edges that now "jump" over w reach u.

Case 4 : u ≤ T w. The redirected edges than "jump" over w reaching s > T w arise from edges between v and s. It follows that s ∈ f T (w). Hence f ′ T (w) = f T (w).

Only Case 1 yields a modification of f T (that replaces v by u in each f T (w) for w < T v) and |f ′ T (w)| ≤ |f T (w)|; we have |f ′ T (w)| = |f T (w)| -1 if and only if u ∈ f T (w). The width of (T, f ′ T ) is no larger than that of (T, f T ) and differs by at most one.

  while being simple, G can have pairs of opposite edges. If G is undirected, then edg G is symmetric and |edg G | = 2 |E G | . The undirected graph underlying G is Und(G) with V Und(G) := V G and edg Und(G) := edg G ∪ edg -1

  undirected and Y is a set of vertices of G of cardinality k, then |Ω(X, Y )| ≤ 2 k . If furthermore 1 ≤ m ≤ k and |N G (x)| ≤ m for all x ∈ X, then |Ω(X, Y )| ≤ γ(k, m) = O(k m ) for fixed m. If G is directed,then each edge of Und(G) between x and y can come from three possible configurations of edges between these vertices. Hence, if |Y | = k, we have |Ω(X, Y )| ≤ (1 + 3) k = 2 2k , and if N Und(G) (x) ≤ m ≤ k for all x ∈ X, we have |Ω(X, Y )| < 3 m γ(k, m).

Figure 1 :

 1 Figure 1: A graph G and a normal tree T

Claim

Lemma 5 :

 5 From every normal tree-decomposition (T, f) of a connected graph G, one can construct in time O(|E G | . |N T |) a clean tree-decomposition of G of no larger width.

Definition 7 :

 7 Clique-width (a) Let C be a finite or infinite set of labels. A C-graph is a triple G

  d) := d -{u} for all sets d as above (h(d) := d for all other d ∈ C).

  and u ∈ d, and of the operations --→ add * ,(d,d ′ ) such that (d, d ′ ) ∈ π(H(u 1 ) ⊕ ... ⊕ H(u p )) and u ∈ d ′ , h(d, d ′ ) := (d -{u}, d ′ -{u}) for all pairs (d, d ′ ) as above.

  where A is the composition of the operations add c,d such that d ∈ π(H(u 1 ) ⊕ ... ⊕ H(u p )) and u ∈ d, h(d) := d -{u} for all sets d as above.

  ) Let G be the undirected graph with vertex set [k + 1] ⊎ P where P := P([k + 1]) -[k + 1]. Its edges are ij for 1 ≤ i < j ≤ k + 1, di for all d ∈ P, i ∈ d, and ∅ -{1}. Let T be the normal tree 1(2(...(k + 1(d 1 (∅), d 2 , ..., d p )..

  )), for i = 2, ..., p, H(u) = relab * →c (L p ), where: A i is the composition of the operations add * ,d such that d ∈ π(H(u i )) and u ∈ d, h i (d) := d -{u} for all d as in the definition of A i .

Figure 2 :

 2 Figure 2: A graph of clique-width 2 and tree-width 3.

  b, a i i, h, e d d, c, a j j, e e e, c, a Lemma 21: (1) For every hypergraph H, twd(Bip(H)) ≤ twd(H) + 1 and twd(H) is unbounded in terms of twd(Bip(H)).

Figure 3 :

 3 Figure 3: Bip(H) and the tree T of a tree-decomposition of H.

Figure 4 :

 4 Figure 4: Tree U for Bip(H) of Figure 2.

Figure 4 shows

 4 Figure 4 shows Bip(H) and the tree U for H and T of Figure 3. The edges of U not in Bip(H) are shown with dotted lines. The nodes for hyperedges w and x are inserted between e and c. We could have inserted x below w.

  first, the setsN Bip(H) (u) ∩ f U (e) for u ∈ V H , u < U e: if u = e, then N Bip(H) (u) ∩ f U (e) = N (e) := {e 1 ∈ E H | e ≤ U e1 , e 1 = e}, otherwise, u < T e, and the neighbours of u are hyperedges e 1 < U e < U e, hence, N Bip(H) (u) ∩ f U (e) = ∅; (in the example of Figure 4, we have N(w O ) = {w O , x O } where w O denotes the "circled w" and similarly for x O ; we have N (x O ) = {x O });

  for some vertex w}. Tree-width and clique-width for G and Inc(G) are related as follows: twd(G) ≤ twd(Inc(G)) ≤ twd(G) + 1 and 12 twd(Inc(G)) ≤ 6cwd(Inc(G)) -1 by Theorem 10(2).

The finite automata arising from MSO formulas are much too large to be implemented in the usual way by lists of transitions. In fly-automata, states and transitions are not tabulated but described by means of an appropriate syntax. Each time a transition is necessary, it is (re)computed. Only the transitions necessary for a given term are computed.

As for G[X], the set X need not be a subset of V G . The same holds for X, Y in Ω(X, Y ) below.

that every vertex is in some bag f (u), every edge has its two ends in some bag, and the connectivity condition holds : for every vertex, the nodes u such that f (u) contains it induce a connected subgraph of T .

One can also use nullary symbols a that do not designate any particular vertex. In that case, the vertex defined by an occurrence u of a in the term is u itself. See[START_REF] Courcelle | Graph structure and monadic second-order logic, a language theoretic approach[END_REF], Section 2.52.

It is used implicitely in[START_REF] Corneil | On the relationship between clique-width and tree-width[END_REF], however, we think useful to detail it. See also Section 6 for its use in fly-automata.

The mapping h u can be chosen so that h ′ changes as few labels as possible.

It is possible to decide in linear time if a graph G of tree-width k has clique-width at most m, for fixed k and m [19], but the complicated algorithm does not highlight the structural properties of G ensuring that cwd(G) ≤ m.

The set c is empty if all edges of G incident to u are in H(u). Actually, we know Equality (4) already from the definitions.

0 The mapping f T is "minimal", cf. Definition 1(c).

1 A similar result in[START_REF] Bouvier | Graphes et décompositions[END_REF] states that cwd(S(H)) = O(twd(H) q-1 ) if H is a q-hypergraph and S(H) is Bip(H) augmented with undirected edges between any two vertices of H.1

If G is simple and undirected, then twd(G) = twd(Inc(G)). If G consists of two opposite directed edges, then twd(G) = 1 and twd(Inc(G)) = 2.

[START_REF] Bodlaender | Fixed-parameter tractability and characterizations of small special treewidth[END_REF] AUTOGRAPH can even compute values associated with graphs[START_REF] Courcelle | Computations by fly-automata beyond monadic second-order logic[END_REF], for an example, the number of 3-colorings. It is written in Common Lisp by I. Durand. See http://dept-info.labri.ubordeaux.fr/~idurand/autograph.1 4 A sentence is a logical formula without free variables.

[START_REF] Corneil | On the relationship between clique-width and tree-width[END_REF] By a result of Bodlaender (see[START_REF] Bodlaender | Fixed-parameter tractability and characterizations of small special treewidth[END_REF][START_REF] Downey | Parameterized complexity[END_REF][START_REF] Downey | Fundamentals of parameterized complexity[END_REF]), a tree-decomposition of G of width k can be computed in linear time if there exists one. Hence the variant of (b) where a tree-decomposition is not given but must be computed also holds, but this variant is not a consequence of (a). Furthermore, the linear time decomposition algorithm is not practically implementable.

This work has been supported by the French National Research Agency (ANR) within the IdEx Bordeaux program "Investments for the future", CPU, ANR-10-IDEX-03-02, and also within the project GraphEn started in October 2015. Parts of it have been presented to a worshop on graph decompositions at CIRM (Marseille, France) in January 2015.

(unique) state reached at position ε (the root of the syntactic tree of t). Hence, the membership of t in L(A), the langage accepted by A, is decidable.

The time computation of a deterministic FA A on a term t is Σ{τ A (u) | u ∈ P os(t)} where τ A (u) is the time taken to compute the state p reached at position u by the run of A, plus the time taken to check whether q A (t) ∈ Acc A .

For model-checking, we are interested in cases where t ∈ L(A) if and only if G(t) satisfies the property to check. Note that the same automaton, hence, the same algorithm, works for graphs of any clique-width as C is infinite.

Example 26 : A deterministic fly-automaton A that checks 3-colorability. Let Γ := {1, 2, 3} be the set of colors. Let G be a C-labelled graph. For each mapping γ :

We define ξ(G) as the finite set of finite sets γ such that γ is a proper 3coloring of G (no two adjacent vertices have the same color). For t ∈ T (F C ), we define ξ(t) := ξ(G(t)). Clearly, ξ(t) can be written as a word over C ⊎ Γ ⊎ A where A is the alphabet consisting of (,),{,} and ",". The function ξ satisfies the following inductive property :

such that (a, i) and (b, i) belong to α}, ξ(relab h (t)) = h(ξ(t)) where h replaces in the word ξ(t)

These properties give the transitions of the desired FA A whose set of states is P(P(C × Γ)), identified to a language over C ⊎ Γ ⊎ A, and such that q A = ξ. The transitions are:

All states are accepting except the empty set. The set of all states that can occur in a run over a term in

. Hence, it cannot be listed in a table for useful values of k.

We go back to the general case. We fix C. If ϕ is an MSO sentence, we denote by L(ϕ) the set of terms t ∈ T (F C ) such that G(t) |= ϕ. The proof of Theorem 25 (a) is based on an algorithm MC that constructs, from any ϕ, a equivalent term over F [wd(t)] . Our first experiments with AUTOGRAPH seem to favor the second method.

Constructions of clique-width terms

The definition of clique-width terms given in Section 2.2 is appropriate for bounding clique-width. However, in concrete applications, some constraints on these terms are necessary or useful for limiting computation times of automata.

Here below, we list them and we explain how arbitrary terms can be transformed into equivalent ones that satisfy these constraints.

Constraints on clique-width terms as inputs of FA.

(1) The disjoint union operation ⊕ must take exactly two arguments. To ensure this, we replace any term of the form t 1 ⊕ ... ⊕ t n by t 1 ⊕ (t 2 ⊕ (... ⊕ t n )..)) (cf. the proof of Proposition 8).

(2) All edge addition operations should be useful. There are two cases where an occurrence of such an operation can be removed. First, if in a term --→ add a,b (t), a or b is not in π(t) : the topmost occurrence of --→ add a,b has no effect and can be removed (the proof of Proposition 8 does that actually). The second case is when G(t) contains an edge from an a-labelled vertex to a b-labelled one; then, we say that the term --→ add a,b (t) has a redundancy, and at least one edge addition operation can be removed from t. See [START_REF] Courcelle | Automata for the verification of monadic second-order graph properties[END_REF] for details. These simplications of terms apply to add a,b in similar ways.

(3) The transitions of an FA relative to a relabelling relab h may be difficult to program if h is neither bijective nor elementary. We recall that a relabelling relab h is bijective on a term t, if h is injective on π(t), hence is a bijection : π(t) → h(π(t)). In this case, we have q A(ϕ) (relab h (t)) = h(q A(ϕ) (t)). Hence, relab h [q] → A(ϕ) h(q) if h is injective on the set of labels from C that occur in q and h(q) is obtained by substituting everywhere q each label a by h(a), hence in a straightforward manner.

In the present version of AUTOGRAPH, transitions are defined for elementary relabellings, i.e., for those of the form relab a→b .

Every term relab h (t) can be replaced by relab h ′ (R(t)) where R is the composition of r elementary relabellings, h ′ is injective on π(R(t)) and r is the number of labels a ∈ π(t) such that h(a) = h(b) for some b ∈ π(t) where b is before a in some fixed enumeration of C. Every relabelling can also be expressed as a composition of elementary ones at the cost of using at most one extra label.

Experiments

The constructions of Proposition 8, Theorems 11 and 25(a) have been implemented in AUTOGRAPH and give satisfactory results. The next step is the implementation of Theorem 25(b) via incidence graphs.

Conclusion

For uniformly q-sparse graphs, clique-width is polynomially bounded in terms of tree-width and we have algorithmically efficient transformations of quasi-normal tree-decompositions into clique-width terms witnessing the claimed upper-bounds. We also have linear bounds for planar graphs and incidence graphs. Applications to FPT graph algorithms for checking monadic second-order properties expressed with edge set quantifications are developped in [START_REF] Courcelle | Fly-automata for checking monadic second-order properties of graphs of bounded tree-width[END_REF][START_REF] Courcelle | Fly-automata for checking MSO 2 graph properties[END_REF].

In all our proofs that yield bounds on clique-width in terms of tree-width, the tree T of a given tree-decomposition (see Theorem 11, Algorithm 12 and Proposition 14) is (up to a minor transformation in Algorithm 12) is the syntactic tree of the constructed clique-width term. However, this is not the case for the bound of Assertion (1.2) in Theorem 10, because its proof is based on a difficult result of [START_REF] Wood | On tree-partition-width[END_REF] that restructures T in a complicated way the tree.

We propose three open questions. 1. Let G be a graph given with an optimal tree-decomposition of width k and t be a clique-width term produced by one of the first two algorithms of Section 3. How large is wd(t)cwd(G) ? Is it polynomial in k ? In words, how far from being optimal is the term t. We recall that our algorithms do not use the full power of the edge addition operations. In the example (3) after Theorem 11, we have, for (T ′′ , f T ′′ ), wd(t)cwd(G) = twd(G) -1.

2. Does there exist p < q such that cwd(G) = O(twd(G) p ) for every uniformly q-sparse graph G ? 8 Appendix : Quasi-normal tree-decompositions and minors

We examine how quasi-normal tree-decompositions behave through the graph reductions that yield the minor quasi-order. Let (T, f ) be a quasi-normal tree-decomposition of a graph G. If H is a subgraph of G, then (T, f ′ ) such that f ′ (u) := f (u) ∩ V H is a quasi-normal tree-decomposition of H of no larger width than (T, f).

We now consider H obtained from G by the contraction of an edge between u and v. We assume that v < T u and we build concretely H as follows:

we delete v and the edge (or edges) between u and v, for every w = u, we make any edge between w and v into an edge between w and u (we preserve its direction if G is directed).