Nicolas Bousquet

Marc Heinrich

Computing maximum cliques in B 2 -EPG graphs

EPG graphs, introduced by Golumbic et al. in 2009, are edge-intersection graphs of paths on an orthogonal grid. The class B k -EPG is the subclass of EPG graphs where the path on the grid associated to each vertex has at most k bends. Epstein et al. showed in 2013 that computing a maximum clique in B1-EPG graphs is polynomial. As remarked in [Heldt et al., 2014], when the number of bends is at least 4, the class contains 2-interval graphs for which computing a maximum clique is an NP-hard problem. The complexity status of the Maximum Clique problem remains open for B2 and B3-EPG graphs. In this paper, we show that we can compute a maximum clique in polynomial time in B2-EPG graphs given a representation of the graph.

 on B1-EPG graphs (where the representation was needed).

Introduction

An Edge-intersection graph of Paths on a Grid (or EPG graph for short) is a graph where vertices can be represented as paths on an orthogonal grid, and where there is an edge between two vertices if their respective paths share at least one edge. A turn on a path is called a bend. EPG graphs were introduced by Golumbic, Lipshteyn and Stern in [START_REF] Charles Golumbic | Edge intersection graphs of single bend paths on a grid[END_REF]. They showed that every graph can be represented as an EPG graph. The number of bends on the representation of each vertex was later improved in [START_REF] Heldt | Edge-intersection graphs of grid paths: The bendnumber[END_REF]. EPG graphs have been introduced in the context of circuit layout, which can be modeled as paths on a grid. EPG graphs are related to the knock-knee layout model where two wires may either cross on a grid point or bend at a common point, but are not allowed to share an edge of the grid. In [START_REF] Charles Golumbic | Edge intersection graphs of single bend paths on a grid[END_REF], the authors introduced a restriction on the number of bends on the path representing each vertex. The class B k -EPG is the subclass of EPG graphs where the path representing each vertex has at most k bends. Interval graphs (intersection graphs of intervals on the line) are B 0 -EPG graphs. The class of trees is in B 1 -EPG [START_REF] Charles Golumbic | Edge intersection graphs of single bend paths on a grid[END_REF], outerplanar graphs are in B 2 -EPG [START_REF] Heldt | On the bend-number of planar and outerplanar graphs[END_REF] and planar graphs are in B 4 -EPG [START_REF] Heldt | On the bend-number of planar and outerplanar graphs[END_REF]. Several papers are devoted to prove structural and algorithmic properties of EPG-graphs with a small number of bends, see for instance [START_REF] Alc Ón | On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid[END_REF][START_REF] Asinowski | Some properties of edge intersection graphs of single-bend paths on a grid[END_REF][START_REF] Cohen | Characterizations of cographs as intersection graphs of paths on a grid[END_REF][START_REF] Francis | VPG and EPG bend-numbers of Halin graphs[END_REF].

While recognizing and finding a representation of a graph in B 0 -EPG (interval graph) can be done in polynomial time, it is NP-complete to decide if a graph belongs to B 1 -EPG [START_REF] Cameron | Edge intersection graphs of -shaped paths in grids[END_REF] or to B 2 -EPG [START_REF] Pergel | On Edge Intersection Graphs of Paths with 2 Bends[END_REF]. The complexity status remains open for more bends. Consequently, in all our results we will mention whether the representation of the graph is needed or not. Epstein et al. [START_REF] Epstein | Approximation Algorithms for B 1 -EPG Graphs[END_REF] showed that the k-coloring problem and the k-independent set problem are NP-complete restricted to B 1 -EPG graphs even if the representation of the graph is provided. Moreover they gave 4approximation algorithms for both problems when the representation of the graph is given. Bessy et al. [START_REF] Bougeret | On Independent Set on B 1 -EPG Graphs[END_REF] proved that this there is no PTAS for the k-independent set problem on B 1 -EPG graphs and that the problem is W [START_REF] Alc Ón | On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid[END_REF]-hard on B 2 -EPG graphs (parameterized by k). Recently, Bonomo et al. [START_REF] Flavia | Clique coloring -EPG graphs[END_REF] showed that every B 1 -EPG graph admits a 4-clique coloring and provides a linear time algorithm that finds it, given the representation of the graph.

Maximum Clique problem on EPG graphs. A claw of the grid is a set of three edges of the grid incident to the same point. Golumbic et al proved in [START_REF] Charles Golumbic | Edge intersection graphs of single bend paths on a grid[END_REF] that a maximum clique in a B 1 -EPG graph can be computed in polynomial time if the representation of the graph is given. This algorithm is based on the fact that, for every clique X of a B 1 -EPG graph, either there exists an edge e of the grid such that all the vertices of X contain e, or there exists a claw T such that all the vertices of X contain at least two of the three edges of T . In particular, it implies that the number of maximal cliques in B 1 -EPG graphs is polynomial. Epstein et al. [START_REF] Epstein | Approximation Algorithms for B 1 -EPG Graphs[END_REF] remarked that the representation of the graph is not needed since the neighborhood of every vertex is a weakly chordal graph. When the number of bends is at least 2, such a proof scheme cannot hold since there might be an exponential number of maximal cliques. Indeed, one can construct a complete graph minus a matching in B 2 -EPG (see Figure 1) which has 2 n/2 maximal cliques. So to compute a maximum clique on B k -EPG graphs for k ≥ 2, a new proof technique has to be introduced.

EPG graphs are closely related to two well known classes of intersection graphs, namely k-interval graphs, and k-track interval graphs on which the maximum clique problem have been widely studied. A k-interval is the union of k distinct intervals in the real line. A k-interval graph, introduced in [START_REF] William | On double and multiple interval graphs[END_REF], is the intersection graph of k-intervals. A k-track interval is the union of k intervals on k-distinct lines (called tracks). A k-track interval graph is an intersection graph of k-track intervals (in other words, it is the edge union of k interval graphs on distinct lines). One can easily check, as first observed in [START_REF] Heldt | Edge-intersection graphs of grid paths: The bendnumber[END_REF], that B 3k-3 -EPG graphs contain k-track interval graphs and B 4k-4 -EPG graphs contain k-interval graphs.

Since computing a maximum clique in a 2-interval graph is NP-hard [START_REF] Francis | The Maximum Clique Problem in Multiple Interval Graphs[END_REF], the Maximum Clique Problem is NP-hard on B 4 -EPG graphs. So the complexity status of the Maximum Clique problem remains open on B k -EPG graphs for k = 2 and 3. In this paper, we prove that the Maximum Clique problem can be decided in polynomial time on B 2 -EPG graphs when the representation of the graph is given. The proof scheme of [START_REF] Charles Golumbic | Edge intersection graphs of single bend paths on a grid[END_REF] cannot be extended to B 2 -EPG graphs. Indeed, there cannot exist a bijection between local structures, like claws, and maximal cliques since there are examples with an exponential number of different maximum cliques. Our proof is divided into two main lemmas. The first one ensures that we can separate so-called Z-vertices (vertices that use paths on two rows) from U-vertices (vertices that use edges of two columns). The second ensures that if a graph only contains Z-vertices, then all the maximal cliques are included in a polynomial number of subgraphs; subgraphs for which a maximum clique can be computed in polynomial time.

Coloring B k -EPG graphs. Gyarfás proved in [START_REF] Gyárfás | On the chromatic number of multiple interval graphs and overlap graphs[END_REF] that the chromatic number of k-interval graphs is bounded by a function of the maximum clique using the degeneracy of the graph. In Section 5, we propose a slightly different proof than the one of Gyarfás to prove the degeneracy of B k -EPG graphs. This bounds ensures that there is a polynomial time algorithm that colors the graph with 2(k +1)•χ(G) colors in polynomial time without knowing the representation of the graph, where χ(G) is the chromatic number of G. In particular, it provides a simple coloring algorithm using at most 4 times the optimal number of colors on B 1 -EPG graphs without knowing its representation. It improves the algorithm of [START_REF] Epstein | Approximation Algorithms for B 1 -EPG Graphs[END_REF] where the representation was needed.

A class of graphs C is χ-bounded if there exists a function f such that χ(G) ≤ f (ω(G)) for every graph G of C with ω(G) the size of a maximum clique in G. Combinatorial bounds on the chromatic number of generalizations of interval graphs received a considerable attention initiated in [START_REF] Gyárfás | Covering and coloring problems for relatives of intervals[END_REF]. The bound on the degeneracy of the graph ensures that the class B k -EPG is χ-bounded and χ(G) ≤ 2(k + 1) • ω(G). As a byproduct, it also ensures that graphs in B k -EPG contain either a clique or a stable set of size n 2(k+1) which improves a result of [START_REF] Asinowski | Some properties of edge intersection graphs of single-bend paths on a grid[END_REF] in which they show that every B 1 -EPG graph admits a clique or a stable set of size O(n 1/3 ). An interval graph is an intersection graph of intervals in the line. More formally, vertices are intervals and two vertices are incident if their respective intervals intersect. Let H be an interval graph with its representation. Let u ∈ V (H). The left extremity of u is the leftmost point p of the line such that u contains p. The right extremity of u is the rightmost point p of the line such that u contains p.

Preliminaries

Let G be an EPG graph with its representation on the grid. In what follows, we will always denote by roman letters a, b, . . . the rows of the grid and by greek letters α, β, . . . the columns of the grids. Given a row a (resp. column α) of the grid, the row a -1 (resp. α -1) denotes the row under a (resp. at the left of α). Given a row a and a column α, we will denote by (a, α) the grid point at the intersection of a and α. By abuse of notation, we will also denote by α (for a given row a) the point at the intersection of row a and column α. Let u ∈ V (G). We denote by P u the path representing u on the grid. The vertex u of G intersects a row (resp. column) if P u contains at least one edge of it.

Typed intervals and projection graphs

Let G be a B 2 -EPG graph with its representation on the grid. Free to slightly modify the representation of G, we can assume that the path associated to every vertex has exactly 2 bends. Indeed, if there is a vertex u such that P u has less than two bends, let (a, α) be one of the two extremities of P u . Up to a rotation of the grid, we can assume that the unique edge of P u incident to (a, α) is the horizontal edge e between (a, α) and (a, α + 1). Then create a new column β between α and α + 1, and replace the edge e by two edges, one between α and β on row a, and another one going up at β. This transformation does not modify the graph G. So we will assume in the following that for every vertex u, the path P u has exactly two bends.

A Z-vertex of G is a vertex that intersects two rows and one column. A U-vertex is a vertex that intersects one row and two columns. The index of a vertex u is the set of rows intersected by u. The vertex u contains a in its index if a is in the index of u.

Let u be a vertex containing a in its index. The extremities of u on a are the points of the row a on which P u stops or bends. Since P u has at most two bends, P u has exactly two extremities on a and the subpath of P u on row a is the interval of a between these two extremities. The a-interval of u, denoted by P a u , is the interval between the two extremities of u on a. Note that since the index of u contains a, P a u contains at least one edge. Let α ≤ β be two points of a.

Typed intervals

Knowing that P a u = [α, β] is not enough to understand the structure of P u . Indeed whether P u stops at α, or bends (upwards or downwards) at α, affects the neighborhood of u in the graph. To catch this difference we introduce typed intervals that contain information on the "possible bends" on the extremities of the interval.

We define three types namely the empty type , the d-type and the u-type . A typed point (on row a) is a pair x, α where x is a type and α is the point at the intersection of row a and column α. A typed interval (for row a) is a pair of typed points (x, α) and (y, β) (on row a) with α ≤ β denoted by [xα, yβ]. Informally, a typed interval is an interval [α, β] and indications on the structure of the bends on the extremities. A typed interval t is proper if α = β or if α = β, x = y, and x ∈ { , }.

Let t = [xα, yβ] and t = [x α , y β ] be two typed intervals on a row a. Denote by zγ one of the endpoints of t . We say that t is coherent with the endpoint zγ of t if one of the following holds: (i) γ is included in the open interval (α, β), or (ii) z = , and [α, β] contains the edge of [α , β ] adjacent to γ, or (iii) z = , and zγ ∈ {xα, yβ}. We can remark in particular that if t is coherent with an endpoint zγ, then γ is in the closed interval

[α, β]. The typed interval t contains t if [α , β ] ⊂ [α, β],
and t is coherent with both endpoints of t . The typed interval t intersects t if [α, β] intersects non trivially [α , β ] (i.e. the intersection contains at least one grid-edge), or t is coherent with an endpoint of t , or t is coherent with an endpoint of t. Note that, if t contains t then in particular it intersects t.

Let u be a vertex containing a in its index. The t-projection of u on a is the typed interval [xα, yβ] where α, β are the extremities of P a u and the type of an extremity γ ∈ {α, β} is if P u stops at γ and (resp. ) if P a u bends downwards (resp. upwards) at γ. Note that this typed interval is proper since it contains at least one edge. The path P u contains (resp. intersects) a typed interval t (on a) if the t-projection of u on a contains t (resp. intersects t). By abuse of notation we say that u contains or intersects t. Note that by definition, the path P u contains the t-projection of u on a. Moreover if a vertex u contains a typed interval t = [xα, yβ], then the path P u weakly contains [α, β]. If u intersects t, then the path P u intersects the segment [α, β] (possibly on a single point).

The following simple lemma motivates the introduction of typed intervals.

Lemma 1.

Let G be a B 2 -EPG graph, let u, v be two vertices whose index contain a, and t be a proper typed interval of a. If u contains t and v intersects t, then u and v are adjacent.

Proof. Let t u = [xα, yβ] and t v = [x α , y β ] be the t-projections of u and v respectively. Let t = [x t α t , y t β t ] be the typed interval such that u contains t, and v intersects t.

Then [α t , β t ] ⊆ [α, β], and [α t , β t ]∩[α , β ] = ∅.
This implies in particular that the intersection of [α, β] and [α , β ] is not empty. If this intersection contains a grid edge e, then the paths P u and P v both contain this edge, and u, v are adjacent in G.

If the intersection is reduced to a single point, then, since we have α = β and α = β , we can assume w.l.o.g. that the right endpoint of t v coincide with the left endpoint of t u , i.e. β = α. By assumption on u, we know that α ≤ α t . Additionally, since [α t , β t ] ∩ [α , β ] = ∅, we must have α t = α. Then either t v is coherent with the endpoint xα of t, or t is coherent with the endpoint yβ of t v . We will assume the former, the other case can be treated exactly the same way. Since [α , β ] does not contain the edge at the left of α t , we have necessarily y = . This implies that y = x t , and x t ∈ { , }. Additionally we know that t u is a coherent with the endpoint x t α t of t. Consequently, we have x = x t = y , which implies that both P u and P v bend at α in the same direction, and thus u, v are adjacent in G.

Lemma 2.

Let G be a B 2 -EPG graph. If the t-projections of u and v on a intersect, then uv is an edge of G. Moreover if u and v are two vertices containing a in their index and have no other row in common, then uv is an edge of G if and only if the t-projections of u and v on a intersect.

Proof. Let u and v be two vertices containing a in their index. The first part of the statement is just a corollary of Lemma 1 since v intersects the t-projection of u on a.

Assume that there is no other row b contained in the index of both u and v. And suppose moreover that the t-projections of u and v on a do not intersect. Suppose by contradiction that u and v are adjacent in G. The two vertices cannot share a common edge on row a, otherwise their projections would intersect. By assumption they cannot share an edge on another row. Consequently, they must have a common edge e on a column, and let α this column. By symmetry, we can assume that e is below the row a. Since the paths P u and P v have at most two bends, both path must bend downwards at the intersection of row a and column α, to intersect the edge e. However, this implies that the t-projections of u and v on a intersect, a contradiction.

Projection graphs

Let Y be the subset of vertices of G such that all the vertices of Y contain a in their index. The projection graph of Y on a is the graph on vertex set Y such that there is an edge between u and v if and only if the t-projections of u and v on a intersect. Note that the projection of Y is not necessarily an interval graph since it can contain an induced C 4 (see Fig. 3). We say that a set of vertices Y is a clique on a if the t-projection of Y on a is a clique. Lemma 2, ensures that a clique on a is indeed a clique in the graph G.

In the very simple case where the representation uses only two rows a and b, we have the following lemma: Lemma 3. Let G be a B 2 -EPG graph and G ab be the subset of vertices with index {a, b}. Then G ab induces a 2-track interval graph.

Proof. Let us first prove that the projection graph of G ab on a is an interval graph. Let u be a vertex of G ab and x and y be the endpoints of P a u . The vertex u bends either on x or on y (since its index is {a, b} it has only one vertical segment). We associate to u the segment s u = (x, y] if u bends on y, and [x, y) if it bends on x. Then the t-projection of u and v intersect on a if and only if the intervals s u and s v intersect. Indeed, if both u and v have a bend at the same column α, then they both contain the interval between row a and b on column α because they have the same index {a, b}. Then the projection graph of G ab on a is an interval graph.

By Lemma 2, any edge on the projection on a or b is also an edge of G. Conversely, if there is an edge between u and v then:

• either their a-segments (resp. b segments) intersect on at least one edge, and there is an edge in the projection graph of G ab on a (resp. b),

• or they share the same column. Then since they bend on the same point of the grid and on the same direction, there is an edge between u and v in the projection graphs of G ab on both a and b.

So there is an edge between u and v if and only if their t-intervals intersect on a or intersect on b. Since the t-projections of G ab on both a and b induce interval graphs, the graph G ab is a 2-track interval graph.

Let us end this section with two lemmas that will be widely used all along the paper.

Lemma 4. Let G be a B 2 -EPG graph and Y be a subset of vertices whose index contain a. Suppose that the projection of Y on a is a clique. Then there is a proper typed interval t such that:

• all vertices of Y contain t, Let us prove now by contradiction that the typed interval t is proper. If α = β then t is proper, so we can suppose that α = β. Now assume that the types x and y are distinct or equal to . Up to symmetry, we can assume that x = and y = . Consequently, there exists a vertex v 1 ∈ Y such that P a v1 has left extremity α and either starts on α or bends downwards on α. Similarly, there exists a vertex v 2 ∈ Y such that P a v2 has right extremity β = α and either ends on α or bends upwards on α. But then the t-projection of v 1 and v 2 do not intersect, a contradiction since the t-projection of Y on a is a clique.

•
Let us finally prove the second point. Suppose that u intersects t, then for all y ∈ Y , y contains t, and by Lemma 2 u and y are adjacent in G. Assume now that u does not intersect t. Let us prove that there exists y ∈ Y that is not incident to u. Either P a u = [α , β ] does not intersect [α, β] or it intersects it on exactly one vertex. We moreover know that if α = β then P a u does not contain the edge at the left and at the right of α (otherwise u would intersect t). So, up to symmetry, we can assume that β ≤ α. If β < α then let v be a vertex such that P a v has leftmost extremity α (such a vertex exists by definition of α). The projections of u and v on a do not intersect and Lemma 2 ensures that u is not adjacent to v.

Assume now that P a u intersects [α, β] on a single point. Since P a u contains at least one edge, this point is either α or β, α say. Let x u be the type of β . Since u does not intersect t, this means that either x u = x or x u = x and x u = . Up to symmetry, we can assume x u = and x = . So there exists v ∈ Y such that P a v has a left extremity at α and P v either bends upwards at α or has no bend at α. Since x u = , P a u has right extremity α and either bends downwards at α or has no bend at α. So the projections of u and v on a does not intersect. By Lemma 1, u and v are not adjacent in G.

Lemma 5.

Let G be a B 2 -EPG graph and Y be a subset of vertices with index {a, b}. Suppose that the projection of Y on a is not clique. Then there is a proper typed interval t such that:

• All vertices of Y intersect t,
• Let u be a vertex with index {a} or {a, c} where c = a, b. Then u is complete to Y if and only if u contains t.

Proof. Let β be the rightmost left extremity of an a-interval of Y , and α be the leftmost right extremity of an a-interval of Y . Since the projection of Y on a is not a clique, α ≤ β. Let Y α be the subset of vertices of Y whose a-segment have right extremity α, and Y β be the subset of vertices of Y with left extremity β. We consider the typed interval t given by t = [xα , yβ ] where:

• x is equal to (resp. ) if all vertices of Y α bend upwards (resp. downwards) at α, and is equal to otherwise,

• similarly, y is equal to (resp. ) if all vertices of Y β bend upwards (resp. downwards) at α, and is equal to otherwise,

• if x = then α = α, otherwise α = α -1, • if y = then β = β, otherwise β = β + 1.
Let us prove that t is a proper typed interval. We can assume w.l.o.g. that a is below b. If α = β then [α , β ] is non reduced to a single point and then t is proper. So we can assume that α = β . In the construction, if one of x or y is equal to , then α = β and then t is proper. Additionally, since all vertices have index {a, b}, and a is below b, all vertices bend upwards on row a. Consequently, x and y cannot be equal to . If none of them is , then they are both , and again t is proper.

We will first prove that every vertex of Y intersects t. Let v be a vertex of Y α , then either α = α -1 and then P a v contains the edge [α -1, α] and thus v intersects t, or α = α. In that case, x is equal to (resp. ) if all the vertices of Y α bends upwards (resp. downwards) on α. But then the t-projection of v has a right endpoint with extremity α and type (resp. ), and then by definition, the t-projection of v is coherent with the endpoint xα of t, and v intersects t. A similar proof holds to show that t-projections of vertices of

Y β intersect t. Now let v ∈ Y \ (Y α ∪ Y β ).
The left extremity of v is before α and its right extremity is after β. Let α v and β v be the left and right extremities of P a v . They satisfy α v ≤ α and

β v ≤ β. If α = α, then α is contained in the open interval (α v , β v )
, and the t-projection of v on a is coherent with the extremity xα of t, and by consequence v intersects t. If α = α -1, then the t-projection of v weakly contains [α , β ], and this interval is not reduced to a single point. Consequently v intersects t.

Let us now prove the second point. Let u be a vertex such that the index of u contains a and not b. If u contains t, then for any y ∈ Y , y intersects t, and by Lemma 2 u and y are adjacent in G.

Assume now that u does not contain t. We will show that there is a y ∈ Y such that u and y are not adjacent in G. By Lemma 1, it suffices to show that there exists a vertex v such that the t-projections of u and v on a do not intersect. First suppose that P u does not weakly contain [α , β ]. We can assume w.l.o.g. that P u does not contain α . Let α u and β u be the left and right endpoints of P a u . If β u < α , then there is a vertex v ∈ Y β such that the left endpoint of P a v is β, and α u < α ≤ α ≤ β. Consequently the t-projection of u and v do not intersect. Otherwise, we can assume α u > α . If α = α, then there is a vertex v ∈ Y α such that the right endpoint of P a v is α. Then, since α = α < α u , the t-projection of u and v do not intersect, and by Lemma 1, u and v do not intersect. If α = α -1, then there is a vertex v such that α is the right endpoint of P a v , and P v stops at α. Since α < α u , we have α ≤ α u . This implies that [α u , β u ] does not contain the edge at the left of α, which implies that the t-projection of u is not coherent with the right extremity of the t-projection of v. The same arguments show that the t-projection of v on a is not coherent with the endpoints of the t-projection of u, and thus the t-projections of u and v do not intersect.

Suppose now that [α u , β u ] weakly contains [α , β ]. Let t u be the t-projection of u. Since u does not contain t, t u is not coherent with one of its endpoints, say α up to symmetry. Then we have α ∈ {α u , β u }. Suppose by contradiction that x = . Then we can't have α = β u since otherwise t would not be proper. So necessarily α = α u , but this implies that t u is coherent with the endpoint α since [α u , β u ] contains the edge at the left of α , a contradiction. Since a is below b, we must have x = . If α = α u , then since t u is not coherent with the endpoint α of t, necessarily the right endpoint of t u has type . Then, if v ∈ Y α , then by construction of t, since x = we have α = α, and α u is the right endpoint of P u v . Since P u does not bend upwards at α, the t-projections of u and v do not intersect. If α = α u , then α = β , and since t is proper, we necessarily have y = . A similar argument shows that there exists v ∈ Y β whose t-projection does not intersect t u .

Maximum clique in B 2 -EPG graphs 4.1 Graphs with Z-vertices

We start with the case where the graph only contains Z-vertices. We will show in Section 4.2 that it is possible to treat independently Z-vertices and U-vertices. The remaining part of Section 4.1 is devoted to prove the following theorem. Theorem 6. Let G be a B 2 -EPG graph with a representation containing only Z-vertices. The size of a maximum clique can be computed in polynomial time.

Note that, up to rotation of the representation of G, this theorem also holds for U-vertices. In other words, the size of a maximum clique can be computed in polynomial time if the graph only contains Uvertices.

The proof of Theorem 6 is divided in three steps. We will first define a notion of good subgraphs of G, and prove that:

• there is a polynomial number of good subgraphs of G and,

• a maximum clique of a good graph can be computed in polynomial time,

• and any maximal clique of G is contained in a good subgraph.

Recall that a clique is maximum if its size is maximum. And it is maximal if it is maximal by inclusion. The first point is an immediate corollary of the definition of good graphs. The proof of the second point consists in decomposing good graphs into sets on which a maximum clique can be computed efficiently. The proof of the third point, the most complicated, will be divided into several lemmas depending on the structure of the maximal clique we are considering.

An induced subgraph H of G is a good graph if one of the following holds:

(I) there are two rows a and b, and two proper typed intervals t a and t b on a and b respectively such that H is the subgraph induced by vertices v such that, v contains t a , or v contains t b , or v intersects both t a and t b , (II) or there are three rows a, b, and c, and three proper typed intervals t a , t b , and t c on a, b, c respectively such that H is the subgraph induced by vertices v such that, either v contains t a , or v contains t b , or v intersects t b and contains t c .

Lemma 7.

Let G be a B 2 -EPG graph. There are O(n 6 ) good graphs, and a maximum clique of a good graph can be computed in polynomial time.

Proof. A good graph is defined by two or three typed intervals. At first glance, to define a typed interval we need to choose a row, and then two points on it. So a natural upper bound on the number of typed interval is O(n 3 ). However, we can make a slightly better evaluation. A point of the grid is important if the path of a vertex ends or bends on this point or on a point incident to it. There is a linear number of important points since every path defines a constant number of important points. One can easily notice, given an interval t a on row a, replacing an extremity r of t a by the important point s that is the closest from r on row a does not modify the set of vertices intersecting or complete to t a . Indeed, no path starts, stops or bends on the interval [r, s] on row a. So we can assume that all the endpoints of typed intervals are important points. This implies that there are at most O(n 2 ) typed intervals. As a consequence, there are O(n 4 ) good graphs of type (I), and O(n 6 ) good graphs of type (II).

Let us now prove that a maximum clique can be computed in polynomial time in a good graph. -Since both H a and H b induce cliques, H 1 is the complement of a bipartite graph. Computing a maximum clique in H 1 is the same as computing a maximal independent set in H1 , the complement graph of H 1 which is bipartite. Additionally, computing a maximum independent set in a bipartite graph can be done in polynomial time. Indeed, a maximum independent set is the complement of a minimum vertex cover. In bipartite graphs, a minimum vertex cover can be computed in polynomial time using for instance Linear Programming.

-By Lemma 3, H 2 is a 2-track interval graph, on which a maximum clique can be computed in polynomial time [START_REF] Francis | The Maximum Clique Problem in Multiple Interval Graphs[END_REF].

Consequently, a maximum clique of both H 1 and H 2 , and then of H, can be computed in polynomial time.

• The remaining part of Section 4.1 is devoted to prove that any maximal clique of G is contained in a good graph. Lemma 8. Let G be a B 2 -EPG graph containing only Z-vertices, and X be a clique of G. Assume that there are two rows a and b such that every horizontal segment of X is included in either a or b, then X is contained in a good graph.

Proof. By taking two typed intervals t a and t b consisting of the whole rows a and b, the clique X is clearly contained in a good graph of type (I).

We say that a set of vertices X intersects a column α (resp. a row a) if at least one vertex of X intersects the column α (resp. the row a). If X is a clique of G, and a, b two rows of the grid, we denote by X ab the subset of vertices of X with index {a, b}.

The three following lemmas allow us to prove that all the cliques of a B 2 -EPG graph are included in a good subgraphs. They use the same kind of techniques. The main idea is, using the tools of Section 3, to find typed intervals which describe well the vertices in a clique X.

Lemma 9.

Let G be a B 2 -EPG graph containing only Z-vertices, and X be a clique of G. If there are two rows a and b such that the projection graphs of X ab on a and b are not cliques, then X is included in a good graph.

Proof. Let X be a clique satisfying this property for rows a and b. Let X a be the set of vertices of X \ X ab intersecting row a and not row b, and X b be the set of vertices of X \ X ab intersecting row b and not row a.

First note that X = X a ∪ X b ∪ X ab . Otherwise there would exist a vertex w of type (c, d) such that {c, d} ∩ {a, b} = ∅ in X. Since w is complete to X ab , w would intersect all the vertices of X ab on their vertical part. But the projection graph of X ab on a is not a clique, consequently X ab intersects at least two columns. Thus a vertex of X ab does not intersect the unique column of w, a contradiction.

By Lemma 5 applied to X ab on both a and b, there exist two typed intervals t a and t b on rows a and b such that every vertex of X ab intersects both t a and t b , and such that vertices of X a contain t a and vertices of X b contain t b . So X is included in a good graph of type (I) defined by t a on a and t b on b. Lemma 10. Let G be a B 2 -EPG graph containing only Z-vertices, and X be a clique of G. If there are two rows a and b such that the projection graph of X ab on a is not a clique, then there is a good graph containing X.

Proof. Let X be a clique satisfying this property for rows a and b. We can assume that the projection graph of X ab on b is a clique since otherwise we can apply Lemma 9. Let X a be the set of vertices of X \ X ab intersecting row a and not row b, and X b be the set of vertices of X \ X ab intersecting row b and not row a.

First note that X = X a ∪ X b ∪ X ab . Otherwise there would exist a vertex w of index {c, d} such that {c, d} ∩ {a, b} = ∅ in X. Since w is complete to X ab , w would intersect all the vertices of X ab on their vertical part. But the projection graph of X ab on a is not a clique, consequently X ab intersects at least two columns. Thus a vertex of X ab does not intersect the unique column of w, a contradiction.

Suppose first that the projection graph of X b ∪ X ab on b is a clique. By Lemma 4 applied to X b on b, there exists a proper typed interval t b on row b such that every vertex of X b contains t b . By Lemma 5 applied to X ab on a, there exists a proper typed interval t a on row a such that every vertex of X a contains t a . So all the vertices of X are contained in the good graph of type (I) defined by t a and t b .

Suppose now that the projection graph of X b ∪X ab on b is not a clique. Then there are two vertices u, v of X b such that the t-projections of u and v on b do not intersect. By Lemma 1, P u and P v intersect another row c, and since the projection graph of X ab on b is a clique, c = a. Since the projection graph of X bc on b is not a clique, and c = a, we can assume that the projection graph of X bc on c is a clique since otherwise Lemma 9 can be applied on X bc . So by Lemma 4 applied to X bc on c, there exists a typed interval t c contained in every vertex of X bc . By Lemma 5 applied to X bc on b (resp. X ab on a), we know that there exists a typed interval t b (resp. t a ) satisfying the two conditions of Lemma 5. Now we divide X b ∪ X ab into two subclasses:

X bc and Y b = (X b ∪ X ab ) \ X bc .
We have X = Y b ∪ X bc ∪ X a . Vertices of X a contain t a . Vertices of X bc intersect t b and contain t c . Vertices of Y b contain t b . This proves that X is included in the good graph of type (II) defined by t a , t b and t c on respectively rows a, b, c.

We now have all the ingredients we need to prove Theorem 6. By Lemma 10, we can assume that for all a, b, the projection graphs of X ab on a and b are cliques. As a by-product, if we denote by X a the set of vertices containing a in their index, then the projection graph of X a on a induces a clique for every row a. Indeed, suppose by contradiction that there is a row a, and two vertices u, v whose index contains a, such that the t-projections of u and v on a do not intersect. Then by Lemma 1, u and v intersect a common row b = a. But then, the projection graph of X ab on a is not a clique, a contradiction. Thus by Lemma 4, for any row a such that X a is not empty, there exists a proper typed interval t a such that the t-projection on a of any vertex of X a contains t a .

Assume that there are two rows a and b such that X ab intersects at least two columns. By Lemma 8, we can assume that X intersects at least three rows. Let w ∈ X \ X ab be a vertex using a third row. As in the proof of Lemma 9, since X ab has at least two columns and w is complete to X ab , w has index either {a, c} or {b, c} for c = a, b. Consequently, w contains either t a or t b , which proves that X is contained in a good graph of type (I).

Assume now that for all pair of rows (a, b), all the vertices of X ab pass through the same column. We can assume that X intersects at least three columns, otherwise we could just rotate the representation of G and apply Lemma 8. Let u, v and w be three vertices using three different columns. Let a, b be the index of u. We can assume w.l.o.g. that the index of v is {b, c}. There are two possible cases:

• w has index {b, d} for some row d. Note that d = a, c since otherwise this would contradict the fact that both X ab and X bc intersect only one column. If all vertices in X contain b in their index, then they all contain the typed interval t b , and X is contained in a good graph of type (I). Let z be a vertex with z ∈ X \ X b . Up to permutations of rows a, c and d, we can assume that the row c is below a and d is below c. Suppose that b is over c. Then, since z must intersect u, v and w, necessarily the index of z is of the form {s 1 , s 2 } with s 1 , s 2 ∈ {a, b, d}. Indeed, z can intersect only one of u, v, w on its vertical part. Additionally, the index of z cannot be {c, d} since otherwise z cannot intersect the vertical part of w. (see Fig. 4). So necessarily the index of z contains a. This proves that every vertex of X contains either t b or t a , and as a consequence X is included in a good graph of type (I). A similar argument shows that if b is below c, then z cannot be of index {a, c}, and the index of z contains d.

• w does not contain b in its index, then w has necessarily index {a, c} in order to intersect both u and v. If there are two rows, say for example a and b, such that every vertex of X has an index containing either a or b, then every vertex of X contains either t a or t b . This implies that X is contained in a good graph of type (I). Suppose that there are no two rows such that the index of any vertex contains one of the two rows. Suppose w.l.o.g.. that row b is below a, and c below b. There is a vertex z c whose index does not contain a or b. Then necessarily, the index of z c is {c, d c } for a certain row d c . Additionally, z c must intersect the vertex u of index {a, b} on its vertical part. This implies that b is below d c . By a similar argument, there is a vertex z a of index {a, d a } with d a = b, c. Then z a must intersect v on its vertical part, and d a is below b. In particular, d a is different from d c . This implies that z a and z c do not have a row or a column in common, and thus do not intersect. Since X is a clique, this case is not possible.

General B 2 -EPG graphs

In Section 4.1, we have seen how to compute a maximum clique in a graph containing only Z-vertices. This section is devoted to prove that we can actually separate the graph in order to assume the graph only contains Z-vertices or U-vertices. We start by proving two lemmas showing that the existence of U-vertices puts some constraints on the Z-vertices that can be appear in a clique. We will then use these two lemmas to prove our main theorem.

Lemma 11. Let G be a B 2 -EPG graph with a representation, and X be a clique of G, then:

• either there are 3 rows intersecting all the U-vertices of X its unique column. Let γ be the unique column intersected by u. All the vertices of X must intersect γ since otherwise u cannot be complete to X. Then γ ∈ {α, β}, and w.l.o.g., we can assume γ = α. Then Lemma 4 ensures that u intersects t α since the unique column of u is α.

The two previous lemmas are the main ingredients to prove that a maximum clique in B 2 -EPG graphs can be computed in polynomial time. The idea of the algorithm is, using Lemma 12, to guess some typed intervals contained in the U-vertices of the clique. Lemma 11 ensures that we do not have to guess too many intervals. Once we have guessed these intervals, we are left with a subgraph which is actually the join of two subgraphs, one with only Z-vertices, and another with only U-vertices. Then the maximum clique is obtained by applying Theorem 6 to each of the components.

Theorem 13. Given a B 2 -EPG graph G with its representation, there is a polynomial time algorithm computing the maximum clique of G.

Proof. In the rest of this proof, S i will denote a set of typed intervals. A vertex u contains S i if u contains all the typed intervals of S i . And u intersects S i if u intersects one of its typed intervals. Given k of these sets S 1 , S 2 , . . . S k , we denote by G(S 1 , S 2 , . . . S k ) the subgraph induced by the set of U-vertices containing one of the S i and the set of Z-vertices intersecting all of the S i -s.

Let X be a clique of G. Let us show that there are at most three sets S 1 , . . . , S k with k ≤ 3 such that X is contained in G(S 1 , . . . , S k ). Free to rotate the representation by 90 • if needed, Lemma 11 ensures that there are at most three rows intersecting all U-vertices. Let us denote by a 1 , a 2 , a 3 these (at most) three rows. By Lemma 12 applied on each row a i , there exists a set of typed intervals S i such that every U-vertex of X intersecting a i contains S i , and every Z-vertex of X intersects S i . This implies that X is included in G(S 1 , . . . , S k ) with k ≤ 3.

Let us now describe the algorithm that computes a maximum clique in G: guess the sets S 1 , . . . S k by trying all possibilities, and then compute the maximum clique of G(S 1 , . . . S k ). Reusing the argument in the proof of Lemma 7, we know that there are at most O(n 2 ) typed intervals. Since each set S i is composed of three typed intervals, this give at most O(n 6 ) possibilities. By looking more precisely at the proof of Lemma 12 we can see that the vertical typed intervals share a common endpoint with the horizontal one. This means that actually you only have O(n 3 ) possibilities to look at for a set S i . Now, since we need at most three of these sets, there are at most O(n 9 ) possible choices for the sets S 1 , . . . S k , k ≤ 3.

To complete the proof of the theorem, we only need to prove that computing a maximum clique in a subgraph G(S 1 , . . . , S k ) can be done in polynomial time. Fix S 1 , . . . S k sets of typed intervals, and denote H = G(S 1 , . . . , S k ). Let H Z (resp. H U ) be the subgraph of H induced by the Z-vertices (resp. U-vertices). Then H is the join of H U and H Z . Indeed, let u a U-vertex of H, and v a Z-vertex of H. By construction, there is a set S i such that u contains S i . Since v intersects S i , by Lemma 1 u and v are adjacent in H. By Theorem 6, a maximum clique of H U and a maximum clique of H Z can be computed in polynomial time. This implies that a maximum clique of H can be computed in polynomial time.

Colorings and χ-boundedness

We denote by χ(G) the chromatic number of G, i.e. the minimum number of colors needed to properly color the graph G. And we denote by ω(G) the maximum size of a clique of G. The following lemma upper bounds the number of edges in a B k -EPG. A similar bound on the number of edges was proposed by Gyarfás in [START_REF] Gyárfás | On the chromatic number of multiple interval graphs and overlap graphs[END_REF] for k-interval graphs. We nevertheless give the proof for completeness. Lemma 14. Let G be a B k -EPG graph on n vertices. There are at most (k + 1)(ω(G) -1)n edges in G.

Proof. Let G be a B k -EPG graph, and consider a representation of G. Let q be the maximum number of distinct paths going through one edge of the grid. Then q ≤ ω(G) since all the paths sharing a common edge of the grid forms a clique of G. Let us prove that G has at most (k + 1)(q -1) edges.

The path P u of u can be decomposed into at most (k + 1) intervals where an interval is a maximum subpath of P u between two bends or between the beginning or the end of P u and the first or last bend.

Each interval is then contained on a single row or on a single column. Note that two intervals of P u can be included on the same row if k is large enough. If two intervals of P u on a row intersect, we define replace both intervals with a single interval that is the union of the two intervals. This operation is called a merging. Given a vertex u, the canonical intervals of u are the intervals of u where we merged all the intervals that have an edge in common.

Let G i = (V i , E i ) be the interval graph where the vertices of G i are the canonical intervals included in the ith row of the representation of G. And there is an edge between two canonical intervals if they intersect non trivially. Note that each path P u might contribute to several vertices in G i but all these intervals have to be disjoint intervals are canonical. Note that the graph G i defines an interval graph. Similarly we define G j for each column of the representation. We denote by G s the graph defined as the disjoint union of all the G i s and of all the G j s. We claim the following: Proof. Let uv be an edge of G. Then P u and P v share an edge and then there is a canonical interval i of P u and a canonical interval j of P v such that i and j intersect. We can associate to uv the edge ij. This function from E(G) to E(G s ) is clearly injective and then |E(G s )| ≥ |E(G)| . Assume by contradiction that there is a clique of size more than q in G i . Then there exists an edge of row i containing at least q + 1 canonical intervals. Since there are at most q different vertices of G going through the same edge, two intervals are associated to the same vertex, a contradiction with the fact that the intervals are canonical.

The remaining of the proof consists in evaluating the number of edges in G . Now the graphs G i and G i are interval graphs, consequently their number of edges satisfies: |E(G i )| ≤ (q -1)|V (G i )|. Since each path is composed of at most (k + 1) intervals, we get:

|E(G)| ≤ i |E(G i )| + j |E(G j )| ≤ (q -1)   i |V (G i )| + j |V (G j )|   = (q -1)(k + 1)n
A graph is k-degenerate if there is an ordering v 1 , . . . , v n of the vertices such that for every i, |N (v i ) ∩ {v i+1 , . . . , v n }| ≤ k. It is straightforward to see that k-degenerate implies (k + 1)-colorable. Lemma 14 immediately implies the following: Corollary 15. Let G be a B k -EPG graph:

• The graph G is 2(k + 1)ω -1 -degenerate.

• χ(G) ≤ 2(k + 1)ω(G).

• There is a polynomial time 2(k + 1)-approximation algorithm for the coloring problem without knowing the representation of G.

• Every graph of B k -EPG contains a clique or a stable set of size at least

Figure 1 :

 1 Figure 1: A complete graph K 6 minus a matching.

  Let a, b be two real values with a ≤ b. The (closed) interval [a, b] is the set of points between a and b containing both a and b. The interval that does not contain b is represented by [a, b) and the one that does not contain a by (a, b].

Figure 3 :

 3 Figure 3: In this example, the projection graph on row a of the four vertices is an induced cycle of length four.

Figure 4 :Figure 5 :

 45 Figure 4: A vertex z with index {c, d} cannot intersect u since the vertical part of u is not between rows c and d.

Claim 1 .

 1 |E(G s )| ≥ |E(G)| and ω(G s ) = q.

n 2 (

 2 k+1) . Proof. The first three points are immediate corollaries of Lemma 14. Let us only prove the last point. If the graph does not admit a clique of size at least n 2(k+1) , thenχ(G) ≤ 2(k + 1) • n 2(k + 1) ≤ 2(k + 1)n.Since a proper coloring is a partition into stable sets, there exists a stable set of size at least ) which concludes the proof.

  Figure2: Examples of typed intervals on the same row. In this example, the interval t 3 is reduced to a single point. The interval t 2 is coherent with the right extremity of t 1 , the extremities of t 3 and the left extremity of t 4 . It is not coherent with the extremities of t 5 . Moreover, t 2 intersects t 1 , t 3 and t 4 but not t 5 . And t 2 contains t 3 .

	t 1	t 2	t 3	t 5
			t 4
	The path P a u intersects non-trivially [α, β] if P a u ∩ [α, β] is not empty or reduced to a single point. The path P a u weakly contains [α, β] if [α, β] is contained in P a u .

  if u is a vertex with index {a} or {a, c} where c is not in the index of any vertex of Y , then u is complete to Y if and only if u intersects t.

Proof. Let α be the rightmost left extremity of an a-interval of Y , and β be the leftmost right extremity of an a-interval of Y . Since the projection of Y on a is a clique, α ≤ β. Let Y α be the set of vertices of Y whose a-segment have left extremity α, and Y β be the set of vertices of Y whose a-segment have right extremity β. We define the typed interval t = [xα, yβ] where x is equal to (resp. ) if all the vertices of Y α bend upwards (resp. downwards) at α, and is equal to otherwise. Similarly, y is equal to (resp. ) if all the vertices of Y β bend upwards (resp. downwards) at α, and is equal to otherwise. Let us prove that t satisfies the conclusion of the lemma.

One can easily check that, by construction, all the vertices of Y contain the typed interval t. Indeed [α, β] is contained in all the intervals P a v for v ∈ Y by definition of α and β.

•

  Let H be a good graph of type (I) defined by two proper typed intervals t a and t b . Let H a be the subset of vertices containing t a , and H b be the set of vertices containing t b , and H ab be the other vertices of H (intersecting both t a and t b by definition of H). By Lemma 1, both H a and H b are complete to H ab and both H a and H b are cliques. Let H 1 be the graph induced by H a ∪ H b , and H 2 be the graph induced by H ab . Then H is the join of H 1 and H 2 (i.e. there is an edge between any vertex of H 1 and any vertex of H 2 ). So a maximum clique of H is the union of a maximum clique of H 1 and a maximum clique of H 2 . Moreover:

  Let H be a good graph of type (II) defined by three proper typed intervals t a , t b and t c . Let H a and H b be the set of vertices containing t a and t b respectively, and H bc be the set of vertices intersecting t b and containing t c . By Lemma 1, H a , H b , and H bc are cliques since for each of these sets there is a proper typed interval contained in every vertex of the set. Moreover H bc is complete to H b since vertices of H b contain t b and vertices of H bc intersect it. Let H 1 = H a and H 2 = H b ∪ H ab . Both H 1 and H 2 induce cliques. So H is the complement of a bipartite graph, and a maximum clique of H can be computed in polynomial time.

* Supported by ANR Projects STINT (ANR-13-BS02-0007) and LabEx PERSYVAL-Lab (ANR-11-LABX-0025-01). † Supported by the ANR-14-CE25-0006 project of the French National Research Agency

• or there are three columns intersecting all the Z-vertices of X.

Proof. Let u 1 , u 2 , u 3 , and u 4 be four U-vertices of X intersecting pairwise different rows. Let us prove that there are three columns containing every Z-vertex of X.

First assume that there are three columns α, β, γ such that, the set of columns intersected by u i is in {α, β, γ} for every i ≤ 4. Let us prove that these three columns intersect every Z-vertex of X. Assume by contradiction that there exists v in X that does not intersect α, β and γ. Then for every i, P v shares an edge with P ui on a horizontal segment. Since all the u i have disjoint index, this would imply that v intersects four different rows, a contradiction.

So we can assume that u 1 , u 2 , u 3 , u 4 intersect at least four columns. Let α and β be the columns of u 1 . We can assume w.l.o.g. that u 2 intersects the columns α and γ, with γ = α, β. And that u 3 intersects a fourth column δ = α, β, γ. So both u 3 and u 4 must intersect α since they must intersect both u 1 and u 2 . Let τ be the second column intersected by u 4 . Then any Z-vertex of X intersects one of α, δ, τ . Indeed, suppose by contradiction that a Z-vertex v of X does not intersect one of these columns. Since P v does not intersect P u3 and P u4 on their vertical intervals, it shares an edge with P u3 and P u4 on their two horizontal parts. Since u 1 , u 2 , u 3 , u 4 have pairwise different index, P v that intersect the row of u 3 and the row of u 4 , share an edge with P u1 on the column β and P u2 on the column γ since v does not intersect column α. However, a Z-vertex intersects a single column, a contradiction.

In Section 3, we have introduced typed intervals. These typed interval defines intervals on a given row. In the following claim, we need two typed of typed interval: horizontal and vertical typed interval. An horizontal typed interval is a typed interval as defined in Section 3. A vertical typed interval is a typed interval of the graph after a rotation, i.e. the graph where rows become columns and columns become rows.

Lemma 12.

Let G be a B 2 -EPG graph with its representation, and X be a clique of G containing only U-vertices with the same index {a}. There exists a set S t of at most three typed intervals such that:

• S t contains exactly one horizontal typed interval, and at most two vertical typed intervals,

• every vertex of X contains all the typed intervals of S t ,

• a Z-vertex u is complete to X if and only if u intersects one of the typed intervals of S t .

Proof. Since X is a clique of G and X only contains U-vertices of index {a}, Lemma 2 ensures that the projection graph of X on a is a clique. By Lemma 4 applied to X on a, there is a typed interval t such that every vertex of X contains t, and, if u is a vertex containing a in its index, and u is complete to X, then u must intersect t. The typed interval t is the unique horizontal typed interval of S t .

Suppose that there is a column α, such that every vertex of X intersects α. Since all the vertices of X intersect the same row a and X is a clique, the projection graph of X on the column α is a clique. Indeed, since all the vertices of X intersect column α and row a, all of them must bend on the point (a, α). Either they all bend on the same direction on column α, say upwards, and then they all contain the edge of the column α between a and a + 1, and the projection graph is a clique. Or, some vertices of X bend upwards and other downwards on (a, α). Since X is a clique, they all come from the same direction on row a and then their t-projections on α pairwise intersect.

By Lemma 4 applied to X on column α, there exists a vertical typed interval t α satisfying both properties of Lemma 4. Since every U-vertex intersects two columns, there are at most two columns α, β for which every vertex of X intersects these columns. Let S t be the set composed of t and the typed intervals t α and t β if they exist.

Let us prove that S t satisfies the conclusion of the lemma. By construction S t contains exactly one horizontal typed interval and at most two vertical typed intervals. By definitions of t and t α , t β , every vertex v of X contains the typed intervals in S t . Let us finally show the last point. Let u be a Z-vertex. If u intersects a typed interval in S t , then by Lemma 1, u is complete to X. Conversely, suppose that u is complete to X. If u contains a in its index, then Lemma 4 ensures that u intersects t since vertices of X all have index {a}. Assume now that the index of u does not contain a. So u intersects al the vertices of X on


Subhandu Rawat

Carlo Cossu
email: carlo.cossu@imft.fr

François Rincon

Travelling-wave solutions bifurcating from relative periodic orbits in plane Poiseuille flow

Keywords:

Travelling-wave solutions are shown to bifurcate from relative periodic orbits in plane Poiseuille flow at Re = 2000 in a saddle-node infinite-period bifurcation. These solutions consist in self-sustaining sinuous quasi-streamwise streaks and quasi-streamwise vortices located in the bulk of the flow. The lower branch travelling-wave solutions evolve into spanwise localized states when the spanwise size L z of the domain in which they are computed is increased. On the contrary, the upper branch of travelling-wave solutions develops multiple streaks when L z is increased. Upper-branch travelling-wave solutions can be continued into coherent solutions to the filtered equations used in large-eddy simulations where they represent turbulent coherent large-scale motions.

Introduction

The dynamics of transitional and turbulent wall-bounded shear flows is the subject of continued interest because of its numerous applications, ranging from drag-reduction for transport applications to the physics of planetary boundary layers. A fruitful line of research has been to apply the dynamical systems approach to the understanding of subcritical transition in wall-bounded shear flows. In this context, the subcritical transition to turbulence has been related to the appearance of invariant solutions to the Navier-Stokes equations disconnected from the laminar basic state, and in particular of travelling-wave (TW) and relative periodic orbit (RPO) solutions. Travelling-wave solutions, representing saddles in phase space, have been found at Reynolds numbers lower than the transitional ones in Couette flow, [START_REF] Nagata | Three-dimensional finite-amplitude solutions in plane Couette flow: bifurcation from infinity[END_REF], plane channel flow [START_REF] Ehrenstein | Three-dimensional wavelike equilibrium states in plane Poiseuille flow[END_REF][START_REF] Waleffe | Homotopy of exact coherent structures in plane shear flows[END_REF], and pipe flow [START_REF] Faisst | Travelling waves in pipe flow[END_REF][START_REF] Wedin | Exact coherent structures in pipe flow: travelling wave solutions[END_REF]. Relative periodic orbit solutions have also been computed in plane Couette flow [START_REF] Clever | Tertiary and quaternary solutions for plane Couette flow[END_REF][START_REF] Kawahara | Periodic motion embedded in plane Couette turbulence: regeneration cycle and burst[END_REF][START_REF] Viswanath | The dynamics of transition to turbulence in plane Couette flow[END_REF], plane channel [START_REF] Toh | A periodic-like solution in channel flow[END_REF], and pipe flows [START_REF] Duguet | Relative periodic orbits in transitional pipe flow[END_REF], and in the asymptotic suction boundary layer [START_REF] Kreilos | Periodic orbits near onset of chaos in plane Couette flow[END_REF]. Global bifurcations of relative periodic orbits have been shown to be related to the transition to chaotic dynamics in plane Couette flow [START_REF] Kreilos | Edge states for the turbulence transition in the asymptotic suction boundary layer[END_REF] and in magnetohydrodynamic Keplerian shear flows [START_REF] Riols | Global bifurcations to subcritical magnetorotational dynamo action in Keplerian shear flow[END_REF].

Invariant solutions are thought to be important not only to understand the subcritical transition, but also to gain understanding of the mechanisms of self-sustained turbulent motions at high Reynolds numbers. In particular, it was shown in a recent study [START_REF] Rawat | On the self-sustained nature of large-scale motions in turbulent Couette flow[END_REF] that the Nagata-Clever-Busse-Waleffe steady solution to the Navier-Stokes equations is connected to a solution to the filtered equations used in large-eddy simulations. This suggests that this coherent steady solution is related to turbulent large-scale motions, which are believed to be the dominant feature of the flow at high Reynolds numbers.

In a previous study [START_REF] Rawat | Relative periodic orbits in plane Poiseuille flow[END_REF], we have computed relative periodic orbit solutions to the Navier-Stokes equations in a plane channel at Reynolds numbers ranging from Re = 2000 to Re = 5000 in a domain periodic in the streamwise and spanwise directions with extension 2 π h × 2 h × 2.416 h, where h is the channel's half-width. These dimensions are typical of large-scale motions in fully developed turbulent flows. The computed solutions occupy the bulk of the flow, even at large Reynolds numbers, similarly to large-scale motions. Other solutions computed in the same flow at high Re do not have this feature, and are most likely relevant to the dynamics in the buffer layer [START_REF] Itano | The dynamics of bursting process in wall turbulence[END_REF][START_REF] Toh | A periodic-like solution in channel flow[END_REF].

The computed relative periodic orbit solutions [START_REF] Rawat | Relative periodic orbits in plane Poiseuille flow[END_REF] displayed the features of lower-branch solutions, which are relevant to the transition problem. In order to track their 'birth' through a bifurcation and to compute the related upper branch solutions (which are expected to provide features more related to the developed turbulent flow), we attempted to continue these solutions to lower Reynolds numbers, but were unable to extend the continuation much below Re = 2000. In an alternative attempt, we therefore also tried to continue the solutions by extending the size of the domain. The main objective of this paper is to show that the periodic solution disappears in an infinite-period saddle-node bifurcation as the box spanwise size is increased, giving birth to two branches of travelling-wave solutions. In the process, we found out that the upper branch displays the features of turbulent large-scale coherent motions and can be continued into a coherent solution to filtered large-eddy simulation equations, while the lower-branch solution evolves into a localized edge-state when the spanwise size of the box is further increased. A summary of the formulation of the problem and of the techniques used to isolate the periodic solutions in a plane channel flow is given in §2. The main results of the continuation are reported in §3, and discussed in §4.

Formulation of the problem and methods

The pressure-gradient-driven flow of an incompressible viscous fluid of constant density ρ and kinematic viscosity ν in a plane channel of height 2 h is considered. The flow satisfies the Navier-Stokes equations:

∇ • u = 0 (1) ∂u ∂t + u • ∇u = -∇ p + 1 Re ∇ 2 u (2)
where the Reynolds number Re = U 0 h/ν is defined with respect to the peak velocity U 0 of the usual laminar (parabolic)

Poiseuille solution. Dimensionless velocities have been defined with respect to U 0 , pressures with respect to ρU 2 0 , lengths with respect to h and times with respect to h/U 0 . The streamwise axis aligned with the pressure gradient is denoted by x, while the wall-normal and spanwise coordinates are denoted by y and z, and u, v and w are the velocity components along x, y and z, respectively. The flow is studied in the domain

[-L x /2, L x /2] × [-1, 1] × [-L z /2, L z /2].
No-slip conditions are enforced in y = ±1 (walls), while periodic boundary conditions are enforced on the other boundaries.

In the final part of the study, new turbulent coherent solutions to the plane Poiseuille flow are sought by solving the dynamical equations for filtered motions routinely used in large eddy simulations [START_REF] Hwang | Linear non-normal energy amplification of harmonic and stochastic forcing in turbulent channel flow[END_REF][START_REF] Hwang | Self-sustained processes in the logarithmic layer of turbulent channel flows[END_REF]. The equations for the filtered motions are the usual ones (see, e.g., [START_REF] Deardorff | A numerical study of three-dimensional turbulent channel flow at large Reynolds numbers[END_REF][START_REF] Sagaut | Large Eddy Simulation for Incompressible Flows: An Introduction[END_REF]):

∂u i ∂x i = 0; ∂u i ∂t + u j ∂u i ∂x j = - ∂q ∂x i + ν ∂ 2 u i ∂x 2 j - ∂τ r ij ∂x j ( 3
)
where filtered quantities are denoted by an over-bar and τ r = τ Rtr(τ R ) I/3, with τ R ij = u i u ju i u j and q = p + tr(τ R )/3.

We use Smagorinsky's [START_REF] Smagorinsky | General circulation experiments with the primitive equations, I: the basic equations[END_REF] subgrid model based on the eddy viscosity ν t for the anisotropic residual stress tensor

τ ij : τ r ij = -2ν t S ij ,
where S ij is the rate of strain tensor associated with the filtered velocity field,

ν t = D(C s ) 2 S and S ≡ (2S ij S ij ) 1/2 ,
= ( x y z ) 1/3 . The Smagorinsky constant reference value is set to C s = 0.05, as in [START_REF] Hwang | Self-sustained process at large scales in turbulent channel flow[END_REF][START_REF] Hwang | Self-sustained processes in the logarithmic layer of turbulent channel flows[END_REF], which is known to provide the best performance for a posteriori tests [START_REF] Härtel | Analysis and modelling of subgrid-scale motions in near-wall turbulence[END_REF]. To avoid non-zero residual velocity and shear stress at the wall we use the wall (damping

) function D = 1 -e -(y + /A + ) 2 with A + = 25.
Travelling-wave solutions are computed with a Newton-based iterative method implemented in the code peanuts [START_REF] Herault | Periodic magnetorotational dynamo action as a prototype of nonlinear magnetic field generation in shear flows[END_REF][START_REF] Riols | Global bifurcations to subcritical magnetorotational dynamo action in Keplerian shear flow[END_REF], which includes parameter continuation, and is also used to analyze the linear stability of the converged solutions. Peanuts relies on repeated calls to numerical time-integrations of the Navier-Stokes or of the filtered equations to perform Newton iterations using a matrix-free iterative method. As in many of previous similar investigations (e.g., [START_REF] Waleffe | Homotopy of exact coherent structures in plane shear flows[END_REF][START_REF] Rawat | Relative periodic orbits in plane Poiseuille flow[END_REF][START_REF] Kreilos | Periodic orbits near onset of chaos in plane Couette flow[END_REF]), the search space of the solutions is restricted to those with mid-plane reflection symmetry {u, v, w}(x, y, z) = {u, -v, w}(x, -y, z), which reduces the number of degrees of freedom and is known to improve convergence. The Navier-Stokes simulations are performed with channelflow, which is based on a Fourier-Chebyshev-Fourier spatial pseudo-spectral discretization [START_REF] Gibson | Visualizing the geometry of state space in plane Couette flow[END_REF]. Solutions are advanced in time using a second-order Crank-Nicolson Runge-Kutta time stepping. Converged solutions were obtained with 32 × 65 × 32 points in the streamwise, wall-normal, and spanwise directions and enforcing a constant volume flux during the simulation. These solutions are almost identical to those computed on a coarser grid 16 × 41 × 16. The numerical results were further tested by recomputing the same periodic solutions on the same grid with the diablo code [START_REF] Bewley | Numerical Renaissance: Simulation, Optimization and Control[END_REF]. diablo was also used to perform the time-integrations of the filtered equations (LES) as in previous related investigations [START_REF] Hwang | Linear non-normal energy amplification of harmonic and stochastic forcing in turbulent channel flow[END_REF][START_REF] Hwang | Self-sustained processes in the logarithmic layer of turbulent channel flows[END_REF][START_REF] Rawat | On the self-sustained nature of large-scale motions in turbulent Couette flow[END_REF].

Results

From relative periodic orbits to travelling waves

In a previous investigation [START_REF] Rawat | Relative periodic orbits in plane Poiseuille flow[END_REF], relative periodic solutions were computed in plane Poiseuille flow in the domain of extension 2 π × 2 × 2.416, for which Waleffe's travelling-wave solutions appear at the lowest Reynolds number [START_REF] Waleffe | Homotopy of exact coherent structures in plane shear flows[END_REF], and for Reynolds numbers ranging from Re = 2000 to 5000. The period T of these solutions increased with the Reynolds number (T = 368 for Re = 2000, T = 739 for Re = 3000, T = 1090 for Re = 4000 and T = 1418 for Re = 5000) and the solutions were found to travel in the streamwise direction with a phase speed C x ≈ 0.98. We have not found it possible to continue these periodic solutions much below Re = 2000, leaving obscure their origin. Previous investigations of plane Couette flow, however, showed that the Nagata-Clever-Busse-Waleffe branch of steady solutions can be connected to a branch of periodic solutions by changing the size of the box [START_REF] Kawahara | Periodic motion embedded in plane Couette turbulence: regeneration cycle and burst[END_REF]. We have therefore continued the relative periodic orbit solution obtained at L z = 2.416 to higher values of L z by using edge-tracking in the ±y symmetric subspace while keeping constant the Reynolds number to Re = 2000 and the streamwise box dimension to L x = 2 π.

When L z is increased the periodic solutions display increasingly long quiescent phases separated by relatively quick bursts, as shown in Fig. 1. This leads to an increase in the period T of the solutions with L z . For values above L z ≈ 3. √ μ, where μ =

(L * z -L z )/L * z .
The divergence of T as μ -1/2 and the O (1) amplitude of the periodic solution while approaching the critical value L * z are the hallmark of the saddle-node infinite-period bifurcation, where a periodic solution is replaced by a pair of fixed points (see, e.g., [START_REF] Strogatz | Nonlinear Dynamics and Chaos: With Applications to Physics[END_REF]). The same type of global bifurcation has already been found, e.g., in the study of axisymmetric convection [START_REF] Tuckerman | Global bifurcation to travelling waves in axisymmetric convection[END_REF] and, more recently, in the homotopy of plane Couette flow travelling-wave solutions that are continued to asymptotic suction boundary layer (ASBL) solutions by increasing the suction velocity on the lower wall [START_REF] Kreilos | Edge states for the turbulence transition in the asymptotic suction boundary layer[END_REF]. In all these cases, including ours, an upper and a lower branch travelling-wave solutions and their spanwise shifted heteroclinically connected copy collide in phase space at L * z , in a pair of saddle-node bifurcations, which results in the formation of a periodic solution, which repeats itself with a shift symmetry every T /2.

Structure of travelling-wave solutions

The flow structures associated with the travelling-wave solution at the bifurcation consist of the usual sinuously bent low-speed streak flanked by a pair of quasi-streamwise vortices, as shown in Fig. 4(a). When this solution is continued to higher values of L z along the lower branch, at least up to L z = 10.5, the streaky structure remains unique and becomes localized in the spanwise direction, leaving an increasingly large portion of the domain almost unperturbed, as shown in Fig. 4(b) and(c)) These localized structures, which arise 'naturally' through continuation without the need to use a windowing function as, e.g., in [START_REF] Gibson | Spanwise-localized solutions of plane shear flows[END_REF], are unstable. For L z = 10.5 the unique unstable eigenvalue found is 5.79 × 10 -3 and is therefore an edge state as can be verified by perturbing the solution along its unstable manifold, i.e. with the unstable eigenfunction. It is indeed found that this perturbation leads to a turbulent state or to a fast decay to the laminar state depending on the sign of the perturbation, as shown in Fig. 5. The observed spanwise localization of the lower-branch solution is similar to that observed in a number of other flows [START_REF] Duguet | Localized edge states in plane Couette flow[END_REF][START_REF] Duguet | Self-sustained localized structures in a boundary-layer flow[END_REF][START_REF] Khapko | Localized edge states in the asymptotic suction boundary layer[END_REF][START_REF] Gibson | Spanwise-localized solutions of plane shear flows[END_REF], and therefore seems to be a generic property of lower-branch solutions in shear flows.

The evolution of the upper-branch travelling-wave solution is completely different. In this case, indeed, continuation to higher values of L z leads to an increase in the number of streaky structures. For instance, at L z = 5.55, as reported in Fig. 6(b), the upper-branch solution contains three low-speed streaks and three pairs of quasi-streamwise vortices, which correspond to a streak spacing λ z ≈ 1.8, in good agreement with the size of large-scale motions (LSM) in the turbulent channel [START_REF] Del Álamo | Spectra of the very large anisotropic scales in turbulent channels[END_REF][START_REF] Hwang | Self-sustained process at large scales in turbulent channel flow[END_REF]. This spacing is confirmed by the analysis of the spanwise premultiplied spectrum of the streamwise velocity (not shown). The energy of the upper-branch solutions increases for increasing L z . In Fig. 7, it can be seen that during the continuation the rms (xz averaged) profiles of the three velocity components preserve a qualitatively similar shape, which is also similar to that of the relative periodic solutions existing before the global bifurcation and this despite the changing nature of the underlying solutions. 3), while (b) and (c) are the lower branch solution respectively computed for L z = 5.55 (empty square symbol in Fig. 3) and L z = 10.5 (empty triangle symbol in Fig. 3). The iso-surfaces at u + = -2 are plotted in green, while red and blue surfaces correspond to positive and negative streamwise vorticity at ω x = ±0.65 max(ω x ). Despite the changing nature of these solutions, it has been impossible to continue the upper branch to values larger than L z ≈ 5.57. The relevance of the upper-branch solution to the dynamics of turbulent large-scale coherent structures is further investigated using filtered large-eddy simulations to include the locally averaged effect of small-scale motions, as discussed in the next section.

Continuation from Navier-Stokes solutions to coherent solutions of the filtered equations

In a recent investigation [START_REF] Rawat | On the self-sustained nature of large-scale motions in turbulent Couette flow[END_REF], it was shown that invariant solutions to the Navier-Stokes equations can be continued to invariant solutions to the equations for filtered turbulent motions used in large-eddy simulations. In the equations used in large eddy simulations, small-scale motions are averaged by filtering and modelled by a sub-grid model. In [START_REF] Rawat | On the self-sustained nature of large-scale motions in turbulent Couette flow[END_REF] Smagorinky's 1963 model [START_REF] Smagorinsky | General circulation experiments with the primitive equations, I: the basic equations[END_REF] was used along the lines of previous investigations of the self-sustained processes at large scale in turbulent shear flows [START_REF] Hwang | Self-sustained process at large scales in turbulent channel flow[END_REF][START_REF] Hwang | Self-sustained processes in the logarithmic layer of turbulent channel flows[END_REF]. In this context, the Smagorinsky constant C s is used as a continuation parameter. The value C s = 0.05 corresponds to large eddy simulations having good a posteriori agreement with direct numerical simulations [START_REF] Härtel | Analysis and modelling of subgrid-scale motions in near-wall turbulence[END_REF], while Navier-Stokes solutions are obtained with C s = 0.

We have therefore continued the travelling-wave upper branch solution from C s = 0 (Navier-Stokes solution) to C s = 0.05, keeping constant the Reynolds number to Re = 2000 and the grid. This corresponds to taking into account the locally averaged effect of dissipative small scale turbulent motions. Proceeding along these lines makes sense because Re = 2000 is more than twice the value of the Reynolds number at which transition is usually observed. The continuation proceeds without major problems and convergence is obtained in less than ten steps in C s . It is found that the introduction of small-scale dissipation does not significantly alter the solutions, except for a slight reduction of the streamwise vorticity and of the streamwise velocity, and for the appearance of the sub-grid eddy viscosity shown in Figs. 8 and9. The computed upper-branch travelling-wave solutions therefore can also be connected to large-scale coherent structures in a fully developed flow. To our knowledge, these solutions are the first coherent invariant solutions to the filtered (LES) equations computed for a plane pressure-driven channel.

Discussion and conclusions

This study has considered invariant solutions in plane Poiseuille flow. The main results can be summarized as follows: -the relative periodic orbit solutions to the Navier-Stokes equations described in Ref. [START_REF] Rawat | Relative periodic orbits in plane Poiseuille flow[END_REF] are connected to two branches of travelling-wave solutions via a global saddle-node-infinite-period bifurcation when they are continued by increasing the spanwise size L z of the numerical domain at Re = 2000, -lower-branch travelling-wave solutions remain spanwise localized when L z is further increased, -upper-branch travelling-wave solutions develop multiple streaks when L z is further increased, -upper-branch solutions are not qualitatively changed when continued from Navier-Stokes solutions into coherent solutions to the filtered equations (used in large-eddy simulations) by increasing the Smagorinsky constant from C s = 0 to C s = 0.05 as in [START_REF] Rawat | On the self-sustained nature of large-scale motions in turbulent Couette flow[END_REF]. In the latter case, these solutions represent turbulent coherent large-scale motions associated with small-scale turbulent dissipation.

Many of these results suggest the existence of some kind of generic dynamics of invariant solutions in wall bounded flows. For instance, the dynamics of the relative periodic orbits from where our continuations start (see also [START_REF] Rawat | Relative periodic orbits in plane Poiseuille flow[END_REF]) is similar to that of relative periodic orbit solutions in the asymptotic boundary layer [START_REF] Kreilos | Edge states for the turbulence transition in the asymptotic suction boundary layer[END_REF] in their T /2 -L z /2 shift property and with their bursting behaviour. Also, the saddle-node infinite-period bifurcation found by increasing L z is of the same type as that found in axi-symmetric Rayleigh-Bénard convection [START_REF] Tuckerman | Global bifurcation to travelling waves in axisymmetric convection[END_REF] or in the bifurcation found by homotopy continuation from Couette's flow to the asymptotic suction boundary layer by [START_REF] Kreilos | Edge states for the turbulence transition in the asymptotic suction boundary layer[END_REF]. The spanwise localization of the lower-branch solution is also in accordance with the results of recent investigations, which revealed the spanwise localization of other lower-branch solutions [START_REF] Schneider | Localized edge states nucleate turbulence in extended plane Couette cells[END_REF][START_REF] Duguet | Self-sustained localized structures in a boundary-layer flow[END_REF][START_REF] Khapko | Localized edge states in the asymptotic suction boundary layer[END_REF][START_REF] Gibson | Spanwise-localized solutions of plane shear flows[END_REF]. One of the most relevant results shown in this study, however, is probably that the upper branch travelling-wave solutions are seen to develop multiple streaks in the spanwise direction when L z is increased and that these solutions preserve their structure in the presence of small-scale dissipation. The wall-normal structure of the upper branch travelling-wave solutions, just as the one of the relative periodic orbits from which they are issued, is reminiscent of large-scale motions in the outer region, even if further work is needed to asses the dynamic relevance of these solutions. Further investigations are needed to determine if other travelling-wave or relative periodic-orbit solutions can be continued to the fully turbulent regime.

Fig. 1 .

 1 Fig. 1. Perturbation energy associated with the relative periodic orbit solutions computed with the edge-tracking procedure for the selected increasing values of the spanwise size L z = 3.525, L z = 3.535, L z = 3.540, L z = 3.548 (panels (a) to (d)). The initial transient before the convergence to the edge state is discarded. Remark the increasing period of the solutions as L z is increased.

  55 the edge tracking converges to a travelling wave (TW) solution instead of a relative periodic orbit. The continuation of the TW solution in L z using pseudo-arclength continuation based on the Newton-based iterations of peanuts reveals the existence of an upper and of a lower branch of solutions connected by a saddle node bifurcation at L * z = 3.55, as shown in Fig.2(a)and in Fig.3.The bifurcation observed at L * z is global and is associated with a divergence of the period T of the periodic solutions while approaching the bifurcation. As shown in Fig.2(b), the data are well matched by the fit T = 240/

Fig. 2 .

 2 Fig. 2. (a) Bifurcation diagram in L z , with L x = 2π and Re = 2000, where the relative periodic orbit solution disappears in a global saddle-node infiniteperiod bifurcation originating a pair of travelling-wave solutions. The periodic solution is reported with its maximum (empty symbols) and minimum (filled symbols) values of the spatially-averaged wall-normal velocity. The symbols correspond to the L z values considered in Fig. 1. The point where the upperand lower-branch travelling-wave solutions are generated is denoted by the X symbol. (b) Variation of time period T close to the bifurcation point. The function T ≈ 240/ √ μ (solid line), where μ = (L * z -L z )/L * z , fits well the data (symbols). The four leftmost symbols correspond to the time-series reported in Fig. 1.

Fig. 3 .

 3 Fig. 3. Continuation diagram for travelling-wave solutions as a function of L z , with L x = 2π and Re = 2000. The left-most part of the diagram is already reported in Fig. 2(a). The turning point where the upper and lower branch of the travelling-wave solution originate corresponds to the saddle-node infinite period global bifurcation.

Fig. 4 .

 4 Fig. 4. Flow fields associated with the travelling-wave solutions corresponding to (a) the saddle node L z ≈ 3.55 (× symbol in Fig.3), while (b) and (c) are the lower branch solution respectively computed for L z = 5.55 (empty square symbol in Fig.3) and L z = 10.5 (empty triangle symbol in Fig.3). The

Fig. 5 .

 5 Fig. 5. Trajectories initialized along the unstable eigendirection of the lower branch spanwise localized travelling-wave solutions (L x = 2π, L z = 10.5, Re = 2000) and represented in the tu (left panel) and uv (right panel) planes respectively. When initialized along one direction of the unstable manifold, the flow rapidly relaxes to the laminar Poiseuille solution (blue line). When initialized in the opposite direction, a turbulent state is attained (green line). This indicates that the lower branch localized state (red cross in the figure) sits on the edge of chaos.

Fig. 6 .

 6 Fig.6. Flow field associated with the upper branch solution computed at L z = 5.55 corresponding to the filled square symbol in Fig.3. The iso-surfaces at u + = -2 are plotted in green, while red and blue surfaces correspond to positive and negative streamwise vorticities at ω x = ±0.65 max(ω x ).

Fig. 7 .Fig. 8 .

 78 Fig. 7. Comparison of the rms velocity profiles of the travelling-wave upper branch solutions for selected values of L z to the rmr profiles of the relative periodic orbit solutions existing for L z < L * z .

Fig. 9 .

 9 Fig. 9. Comparison of the rms velocity profiles of the TW upper branch solutions for C s = 0 and C s = 0.05 (with L z = 5.55 and Re = 2000). In panel (d) is displayed the eddy viscosity ν t /ν associated with the subgrid motions modelled in the solution to the filtered (LES) equations at C s = 0.05.

Acknowledgements

The use of the codes channelflow [25,35], diablo code [26] as well as financial support (grant n. 11050707) from PRES Université de Toulouse and Région Midi-Pyrénées are kindly acknowledged.