Laurent Feuilloley

Michel Habib

Classifying grounded intersection graphs via ordered forbidden patterns

It was noted already in the 90s that many classic graph classes, such as interval, chordal, and bipartite graphs, can be characterized by the existence of an ordering of the vertices avoiding some ordered subgraphs, called patterns. Very recently, all the classes corresponding to patterns on three vertices (including the ones mentioned above) have been listed, and proved to be efficiently recognizable. In contrast, very little is known about patterns on four vertices.

One of the few graph classes characterized by a pattern on four vertices is the class of intersection graphs of rectangles that are said to be grounded on a line. This class appears naturally in the study of intersection graphs, and similar grounded classes have recently attracted a lot of attention.

This paper contains three parts. First, we make a survey of grounded intersection graph classes, summarizing all the known inclusions between these various classes. Second, we show that the correspondence between a pattern on four vertices and grounded rectangle graphs is not an isolated phenomenon. We establish several other pattern characterizations for geometric classes, and show that the hierarchy of grounded intersection graph classes is tightly interleaved with the classes defined patterns on four vertices. We claim that forbidden patterns are a useful tool to classify grounded intersection graphs. Finally, we give an overview of the complexity of the recognition of classes defined by forbidden patterns on four vertices and list several interesting open problems.

Introduction

There are several ways to approach well-structured graph classes, and two important ones are forbidden structures and intersection representations. In a nutshell, this paper is about establishing that there exists a strong relation between a type of forbidden structures and type of intersection representations.

Some classic forbidden structures are forbidden (induced) subgraphs and forbidden minors. In this paper, we will consider another type of forbidden structures, called patterns. A pattern is basically an ordered graph, and we say that a graph avoids a pattern if there exists an ordering of its vertices such that the pattern does not appear [START_REF] Damaschke | Forbidden ordered subgraphs[END_REF][START_REF] Feuilloley | Graph classes and forbidden patterns on three vertices[END_REF]. Various well-known classes have forbidden pattern characterizations, such as chordal, bipartite, comparability, permutation, split and threshold graphs. Characterizations by patterns are very useful. First, they can be more compact and manageable than forbidden induced subgraphs characterizations. Second, they lead to efficient recognition algorithms, often based on graph traversals [START_REF] Hell | Ordering without forbidden patterns[END_REF][START_REF] Feuilloley | Graph classes and forbidden patterns on three vertices[END_REF].

Let us illustrate pattern characterization and their usefulness on the example of interval graphs. A graph on n vertices is an interval graph if there exists a set of n intervals that we can identify to the vertices, such that two intervals intersect if and only if the associated vertices are adjacent. It is well-known [START_REF] Olariu | An optimal greedy heuristic to color interval graphs[END_REF][START_REF] Ramalingam | A unified approach to domination problems on interval graphs[END_REF] that interval graphs can also be characterized by a forbidden pattern. Namely, a graph is an interval graph, if and only if, there exists an ordering of its vertices, such that for any triplet of vertices, a < b < c, it is not the case that (a, c) belongs to the graph, and (a, b) does not. The forbidden pattern of this characterization is depicted in Figure 1.

1 2 3
Figure 1: Representation of the forbidden pattern for interval graphs. The general meaning of the edge styles is that in the forbidden pattern, the plain edges are present, the dashed edges are absent, and if there is no edge between two vertices, there is no constraint.

This pattern characterization is very simple and compact, unlike the forbidden subgraph characterization of interval graphs, which consists in three graphs and two infinite families of graphs [START_REF] Lekkeikerker | Representation of a finite graph by a set of intervals on the real line[END_REF]. Also, thanks to this characterization, interval graphs can be recognized in linear time, because an ordering avoiding the pattern can be computed efficiently via graphs traversals [START_REF] Corneil | The LBFS structure and recognition of interval graphs[END_REF].

Interval graphs are also an example of intersection graphs. In a similar way as for interval graphs, given a set of geometric objects, one can define a graph by associating a node with every object and adding an edge between every two nodes whose geometric objects intersect. By allowing different types of geometric objects one can define different graph classes. Such geometric graphs have been well-studied, partly because they are related with practical algorithmic questions. The example of interval graphs illustrates how patterns and geometry can be related: the ordering of the left endpoints of the intervals, in the intersection representation, is an ordering that avoids the forbidden pattern.

Another example of a known class that is characterized by both a pattern and an intersection model is the class of grounded rectangle graphs. These graphs have been introduced a few years ago in several papers independently, under various names (diagonal-touched rectangle graphs [START_REF] José | Independent and hitting sets of rectangles intersecting a diagonal line: Algorithms and complexity[END_REF], hook graphs [START_REF] Stuart | Hook graphs and more : Some contributions to geometric graph theory[END_REF], max point-tolerance graphs [START_REF] Catanzaro | Max point-tolerance graphs[END_REF], and p-box(1) graphs [START_REF] Soto | p-Box: A new graph model[END_REF]). Grounded rectangle graphs are the intersection graphs of rectangles grounded on a line, whose faces have angles π/4 and 3π/4 with the grounding line. See Figure 2a. As proved independently in several of the papers cited above, this class is characterized by the forbidden pattern of Figure 2b. In other words, a graph is a grounded rectangle graph, if and only if, there exists an ordering of the nodes such that no subset of four nodes a < b < c < d, is such that: (a, c) and (b, d) are edges, and (b, c) is not and edge. Again, the ordering on the grounding line is an ordering that avoids the pattern. Note that the pattern of the interval graphs is included in the pattern of the grounded rectangle graphs. This is not a coincidence: grounded rectangle graphs generalize interval graphs, and this is witnessed by the pattern inclusion. In this paper, we investigate the relations between classes defined by intersecting objects grounded on a line, and classes defined by patterns of a specific shape. Beyond the fact that this connection is intriguing, we have two motivations for this study.

The first motivation comes from the study of patterns. A recent work [START_REF] Feuilloley | Graph classes and forbidden patterns on three vertices[END_REF] established a complete characterization of the classes characterized by a set of forbidden patterns on three nodes. A remarkable fact is that basically all these classes have been studied before, and that they can all be recognized in polynomial time (and for most of them linear time). It is then natural to ask whether patterns on four nodes also define interesting classes that can be recognized efficiently. Answering this question seems very challenging. First, note that there are 3 6 = 729 different patterns on four vertices, thus a priori 2 729 sets of patterns on 4 vertices. Even if many of these classes are equivalent because symmetries, it seems unrealistic to study all these classes exhaustively. Second, we know that the complexity landscape is going to be more complex, as there exists patterns on four vertices that define classes that are NP-hard to recognize. Given this challenge, a reasonable place to start the study of patterns on four vertices is to generalize the geometric-pattern connection of grounded rectangle graphs.

The second motivation is on the geometry side. Establishing that two intersection graph classes are distinct can be a hard task, because it is not always easy to reason about geometric objects. In particular, it might be difficult to be exhaustive in a case analysis. On the other hand, considering an ordering of the nodes can be handy, because these are more combinatorial objects that can be easily enumerated. This also implies that it might be easier to find answers or conjectures by computer simulation.

Overview

Grounded rectangle graphs are just one example of grounded intersection graphs. By changing the shape, and the way the shapes are grounded, one can define and redefine many graph classes. For example, interval graphs correspond to shapes that are segments, and that are grounded on their two extremities. Other examples of wellknown graph classes captured by this framework are permutation, cocomparability and interval filament graphs. Many papers have defined new such classes, and established inclusions or incomparability between them. At this point, it is useful to have a common terminology (which we establish in Section 3), and a systematic survey of the classes and their inclusions (which we do in Section 4).

In Sections 5 to 9, we establish new equalities, inclusions and incomparabilities, between classes defined by forbidden patterns on four vertices and grounded intersection classes. Let us give a simple example illustrating the type of results we get.

Consider a configuration of unconstrained shapes in the plane grounded on a line, like in Figure 3a. We claim that the ordering of the shapes on the line avoids the pattern of Figure 3b. Let us sketch a proof (see Section 8, for a proper proof). Suppose that the pattern appears when we consider the graph with the ordering of the shapes on the line. Consider the two shapes that correspond to position 1 and 3 in the pattern. They define two regions (above the line): the region below the shapes (that we could call the innerface) and the region above the shapes (the outerface). Since 2 is in the innerface, and 4 in the outerface, there should be an intersection between the shapes of numbers {1, 3} and {2, 4}. which contradicts the fact that in the pattern of Figure 3b, no edge is allowed except [START_REF] Cabello | Refining the hierarchies of classes of geometric intersection graphs[END_REF][START_REF] Catanzaro | Max point-tolerance graphs[END_REF] and [START_REF] Cardinal | Intersection graphs of rays and grounded segments[END_REF][START_REF] Corneil | Extensions of permutation and interval graphs[END_REF].

Since we have not yet introduced all the notations, at the moment we cannot describe our results in details. Nevertheless, we will list them, as a roadmap for the paper that the reader can go back to, to get the big picture. Our results are enumerated below, and are illustrated (along with known results) in Figure 4.

• Theorem 1 : The touching grounded L-shape graphs are the forests.

• Theorem 2: The touching grounded string graphs are the outerplanar graphs.

• Theorem 3 (Edges 11 and 14 in Figure 4): Interval filament graphs (that we call bigrounded string graphs) are between C a and C ab in the inclusion hierarchy.

• Theorem 4 (Edge 19 and 22): Grounded stairs graph are between C ab and C abc in the inclusion hierarchy.

• Theorem 5 (Edge 24): Grounded convex graphs are included in C abc .

• Theorem 6 (Edge 27): String graphs (that we call grounded string graphs) are included in C abcd .

• Theorem 7 (Edge 13): C a is strictly included in C ab , and C abcd does not contain all graphs.

The inclusions of grounded stairs and string graphs in, respectively, C abc and C abcd (Edges 22 and 24) can actually be derived from [START_REF] Pach | Ordered graphs and large bi-cliques in intersection graphs of curves[END_REF][START_REF] Pach | On the chromatic number of disjointness graphs of curves[END_REF]. We reprove them in our setting for completeness.

The rest of the inclusions described in Figure 4 correspond to the following observations.

• Observation 10: Edges 3, 9, 10.

• Observation 9: Edge 20.

• Observation 8: Edge 23 and 25.

• Observation 1: Edge 26.

• Observation 11: All the other edges.

We can already make several observations about Figure 4. We can see some classes we have mentioned: in the middle, grounded rectangle graphs and their pattern, and on the bottom interval graphs, and their pattern. The inclusion we have just sketched is the edge labeled 27 C abcd is the name we use for the class of the pattern of Figure 3b). In general, we can see that pattern classes and geometric classes are intriguingly interleaved.

In the last section of the paper (Section 10), we review known results and open questions about the complexity of the recognition of the classes defined by forbidden patterns on four vertices.

Preliminaries

Patterns

We first define formally patterns, and the related concepts. We use the exact same vocabulary as in [START_REF] Feuilloley | Graph classes and forbidden patterns on three vertices[END_REF]. Definition 1. A trigraph T is a 4-tuple (V (T ), E(T ), N (T ), U (T )) where V (T ) is the vertex set and every unordered pair of vertices belongs to one of the three disjoint sets E(T ), N (T ), and U (T ) called respectively edges, non-edges and undecided edges.

A graph G = (V (G), E(G)) is a realization of a trigraph T if V (G) = V (T ) and E(G) = E(T ) ∪ U , where U ⊂ U (T ).
Definition 2. An ordered graph is a graph given with a total ordering of its vertices. We define the same for a trigraph, and call it a pattern. We say that an ordered graph is a realization of a pattern, the ordered graph and the pattern share the same set of vertices, the same linear order, and the graph is a realization of the trigraph.

When drawing a pattern, we will use plain edges for edges, dashed edges for nonedges, and nothing for undecided edges (just like we did in the introduction). Also, in our drawings, the patterns are ordered from left to right. Definition 3. In an ordered graph, if no subgraph is the realization of given pattern, we say that the ordered graph avoids the pattern. Given a family of patterns F, we define the class C F as the set of connected graphs that have an ordering avoiding the patterns in F.

If F consists of only one pattern P , we abuse notation an simply write C P , instead of C {P } . Note that one can equivalently consider forbidden ordered subgraphs instead of forbidden order trigraphs (which are the patterns). Like in [START_REF] Feuilloley | Graph classes and forbidden patterns on three vertices[END_REF], we prefer patterns, because they give more compact characterizations of the obstructions. Table 1 shows a list of graph classes, and their corresponding pattern.

As already noticed in [START_REF] Damaschke | Forbidden ordered subgraphs[END_REF][START_REF] Feuilloley | Graph classes and forbidden patterns on three vertices[END_REF][START_REF] Wood | Characterisations of intersection graphs by vertex orderings[END_REF], inclusions of patterns imply inclusions of classes.

Observation 1. Consider two patterns P and P . We say that P is included in P if V (P ) ⊆ V (P ), E(P ) ⊆ E(P ), and N (P ) ⊆ N (P ). In this case, C P ⊆ C P .

There is one type of pattern that will be important in this paper, and that we define now. [START_REF] Damaschke | Forbidden ordered subgraphs[END_REF]. For each row the class on the first column is characterized by the pattern represented in the second column.

Definition 4. Consider patterns on four nodes {1, 2, 3, 4}. We use the following names for some pairs of nodes: a = (1, 2), b = (2, 3), c = (3, 4), d = (1, 4) (see Figure 5). Let S ⊆ {a, b, c, d}, the pattern P S is the pattern on four vertices, with edges (1, 3) and [START_REF] Cardinal | Intersection graphs of rays and grounded segments[END_REF][START_REF] Corneil | Extensions of permutation and interval graphs[END_REF], and non-edge set S. The class C S is the class where P S is forbidden. Note that we have already mentioned that grounded rectangle graphs correspond to the pattern P b , and we discussed the pattern P abcd at the beginning of Section 2. It is folklore that outerplanar graphs are chacterized by P ∅ .

Grounded types

Definition 5. We say that a configuration of shapes is grounded if it is in one of the two following situation.

• There exists a horizontal straight line such that all the shapes are above the line, and are touching it in at least one point,

• There exists a circle such that all the shapes are inside the circle, and are touching it in at least one point.

We call the line (resp. circle) the grounding line (resp. grounding circle). We also require that no two shapes touch the grounding line/circle on the same point (except for interval graphs, for which we require that the endpoints of the intervals are different). For the case of a grounding line, we can define the grounding ordering as the order in which the shapes touch the line for the first time (from left to right).

We consider six grounding types, that are illustrated Figure 6. Definition 6. A configuration of shapes is:

(a) Grounded, if all the shapes are touching the grounding line at least once. (b) Touching grounded, if it is grounded, and the shapes only intersect on their borders, and not on their interiors. (c) Outer, if it has a grounding circle. (d) Bigrounded, if every shape is touching the line on at least two points, and these two points are extremal in terms of abscissa. (e) 2-Grounded, if there is a second line above the grounding line, an all shapes are contained between the two lines, and touching the two lines. (f) Circle, if it has a grounding circle that every shape touches twice.

Observation 2. The touching grounded configuration is not well-defined for shapes that do not have interiors (e.g. curves). For example, two segments that are crossing are intuitively not considered as touching, although they only intersect at their border. In the following we will use a natural way to differentiate between configurations where curves are touching and where the curves are intersecting. If, when we replace the lines by thick lines (with an interior), the drawing can be kept identical (that is only doing infinitesimal changes) then we will say that it is proper touching representation. If instead, replacing the lines by thick lines transforms the configuration into a drawing that cannot be fixed locally by minor modifications, then we will not consider the configuration as touching.

Relations between grounding types

The different grounding types are related, and some inclusions follow automatically from these relations. Let us list these relations. We refer to a generic shape type S, that we are going to properly defined later, but one can think of S as being segments, convex polygons, lines etc. We start by making a few informal observations, to show how one can transform one grounding type into another. Note that some shapes are more difficult to manipulate, and that some observation work only for some shapes. Observation 3. For every shape S, touching-grounded-S graphs, bigrounded-S graphs and 2-grounded-S graphs are included in grounded-S graphs, because the definitions of the former are more constrained than the definition of the later. For the same reason, circle-S graphs are contained in outer-S graphs. Observation 4. For several shape types S, grounded-S graphs are included in outer-S graphs, and bigrounded graphs are included into circle-S graphs. This is because one can transform a straight line into a small arc of a large circle via a small deformation. If S is stable by such deformation, then we can transfer the intersection representations. See Figure 7 for the case of grounded-S and outer-S configurations.

Observation 5. For several shape types, 2-grounded-S graphs are included into circle-S graphs. This because two parallel lines can be transformed into a slice of a large circle with a small deformation. See Figure 8 Observation 6 ( [START_REF] Fanica | Maximum weight independent sets and cliques in intersection graphs of filaments[END_REF]). For several shape types, 2-grounded-S graphs are included into bigrounded-S graphs. This is because we can take the upper line and plug it to the first line, continuously curving the shapes without creating new intersections. In this case there is a point P on the line such that any shape has one grounding point on the left of P and one grounding point on the right of P . See Figure 9. Observation 7. For several shape types, outer-S graphs are included in grounded-S graphs. This happens when one can cut the circle in one point, and then continuously transform both the circle and the shapes, keeping the same intersections, until the circle is straighten into a line (in a similar way as in the transformation of Observation 6)s.

Shape types

We now list the shapes we are going to use.

Definition 7.

A shape type is one the following 8 cases.

1. Segments.

Triangles.

3. Trapeziums. 4. Diagonal rectangles, that are rectangles touching a grounding line on one corner, and with faces with angles π/4 and 3π/4 with respect to the grounding line. 5. L-shape that are formed by a vertical segment touching the grounding line, and extended by an horizontal segment to the right. 6. Stairs which are series of horizontal and vertical segments forming stairs going to the right. 7. (Convex) polygons. (For this paper all polygons are convex, thus we will simply say "polygons".) 8. Strings which are simply curves.

Observation 8. Strings are more general than all the other shapes. Convex polygons are more general than segments and rectangles.

Survey of grounded intersection graphs

In this section, we make a survey of grounded intersection graphs. The goal is to have a more detailed survey than in previous papers [START_REF] Jelínek | On grounded L-graphs and their relatives[END_REF][START_REF] Davies | Grounded l-graphs are polynomially χ-bounded[END_REF], with a special focus on pattern characterization. It can be seen as an extended related works section.

We study the combinations of the shape types (Definition 7) and grounding types (Definition 6). Some combinations are not mentioned, because they have not been studied, and are not used in this paper either. This section contains eight subsections, one for each shape type of Definition 7. Each subsection contains a list of classes (with some additional remarks, such as pattern characterization) and a list of inclusions with other classes of the survey.

Segments

Classes Grounded segment graphs have been defined in [START_REF] Cardinal | Intersection graphs of rays and grounded segments[END_REF]. It is proved in [START_REF] Cardinal | Intersection graphs of rays and grounded segments[END_REF] that this class is the same as the one of downward rays intersections, where a downward ray is a halfline pointing downward.

The 2-grounded segment graphs are known to be the same as the permutation graphs. A permutation graph is a graph that can be built from a permutation the following way: the vertices represent the elements of a permutation, and the edges represent pairs of elements that are reversed by the permutation. Permutation graphs are characterized by a couple of forbidden patterns [START_REF] Even | Permutation graphs and transitive graphs[END_REF], see Figure 10.

The bigrounded segment graphs are the interval graphs. Indeed, if the segments touch the grounding line by two points, then they are completely contained in the grounding line. As already mentioned in the introduction, interval graphs have pattern characterization, with the pattern of Figure 1. The circle segment graphs are known as circle graphs. It is known that outerplanar graphs are circle graphs [START_REF] Unger | On the k-colouring of circle-graphs[END_REF].

Outer segment graphs are introduced in [START_REF] Cardinal | Intersection graphs of rays and grounded segments[END_REF], where it is proved that this class strictly contains the intersection graphs of rays (that is, of half-lines).

Inclusions.

• Grounded segments graphs contain 2-grounded segment graphs (permutation graphs) and bigrounded segment graphs (interval graphs), by Observation 3. These inclusions are strict (see e.g. [START_REF] Jelínek | On grounded L-graphs and their relatives[END_REF]). • Grounded segments strictly contains grounded L-shapes [START_REF] Jelínek | On grounded L-graphs and their relatives[END_REF].

• Outer-segment graphs contain circle segment graphs, by Observation 3.

• Grounded segment graphs are included into outer-segment graphs, by Observation 4, and this inclusion is strict [START_REF] Cardinal | Intersection graphs of rays and grounded segments[END_REF]. • 2-grounded segment graphs are included in circle segment graphs, by Observation 5, and the inclusion is strict (as witnessed by C 6 ). • By Observation 1, interval graphs are included in outerplanar graphs.

Triangles

Classes. For triangles, we only consider the 2-grounded case, which actually contains two subcases. The point interval graphs (PI-graphs) are the intersection graphs of 2-grounded triangles, where every triangle has an edge on the bottom line. The PI *graph class is the generalization where every triangle has an edge on one of the two lines. Interestingly, PI-graphs can be recognized in polynomial-time [START_REF] Mertzios | The recognition of simple-triangle graphs and of linearinterval orders is polynomial[END_REF], but PI *graphs are NP-complete to recognize [START_REF] Mertzios | The recognition of triangle graphs[END_REF].

Inclusions. PI-graphs contain bigrounded segment (interval) and 2-grounded segment (permutation) graphs, by generalization of the shapes, and the inclusions are strict (see [START_REF] Mertzios | The recognition of triangle graphs[END_REF]).

Trapeziums

Classes The 2-grounded trapezium graphs, where the trapeziums have the two parallel faces on the two lines, are known as trapezoid graphs [START_REF] Dagan | Trapezoid graphs and their coloring[END_REF].

Circle-grounded trapezium graphs can be defined as intersections of regions of the circle defined by two non-crossing cords. These are known as circle trapezoid graphs [START_REF] Felsner | Trapezoid graphs and generalizations, geometry and algorithms[END_REF].

Inclusions The 2-grounded trapezium graphs are included in the circle trapezium graphs, via Observation 5, and the inclusion is strict [START_REF] Felsner | Trapezoid graphs and generalizations, geometry and algorithms[END_REF]. The 2-grounded trapezium graphs contain PI * graphs by the preliminary observations, and the inclusion is strict [START_REF] Corneil | Extensions of permutation and interval graphs[END_REF].

(Diagonal) rectangles

Classes. Grounded diagonal rectangles graphs are known under various names as already mentioned in the introduction: diagonal-touched rectangle graphs [START_REF] José | Independent and hitting sets of rectangles intersecting a diagonal line: Algorithms and complexity[END_REF], hook graphs [START_REF] Stuart | Hook graphs and more : Some contributions to geometric graph theory[END_REF], max point-tolerance graphs [START_REF] Catanzaro | Max point-tolerance graphs[END_REF], and p-box(1) graphs [START_REF] Soto | p-Box: A new graph model[END_REF]. In particular this class can be also obtained as intersection of diagonal orthogonal triangles or even diagonal L-shapes. This class is characterized by the pattern P b (see Figure 2b).

Inclusions. Grounded diagonal rectangles graphs strictly contain interval graphs and outerplanar graphs [START_REF] Catanzaro | Max point-tolerance graphs[END_REF].

L-shapes

Class. Grounded L-shapes were introduced in [START_REF] Mcguinness | On bounding the chromatic number of l-graphs[END_REF]. It was proved in [START_REF] Jelínek | On grounded L-graphs and their relatives[END_REF] that these graph have a pattern characterization with the two patterns of Figure 11. The first of the two patterns says that on a set of nodes 1 < 2 < 3 < 4, it is not possible to have edges [START_REF] Cabello | Refining the hierarchies of classes of geometric intersection graphs[END_REF][START_REF] Catanzaro | Max point-tolerance graphs[END_REF] and [START_REF] Cardinal | Intersection graphs of rays and grounded segments[END_REF][START_REF] Corneil | Extensions of permutation and interval graphs[END_REF], but not (1, 2) and (2, 3) (this is what we call P ab ). The second pattern says that it is not possible to have edges (1, 2), [START_REF] Cardinal | Intersection graphs of rays and grounded segments[END_REF][START_REF] Catanzaro | Max point-tolerance graphs[END_REF] and [START_REF] Cabello | Refining the hierarchies of classes of geometric intersection graphs[END_REF][START_REF] Corneil | Extensions of permutation and interval graphs[END_REF] but not (1, 3). Inclusions.

• Because the L-shapes can only be grounded on the lowest point, the outer-Lshape graphs are the same as the grounded-L-shape.

• The circle-L-shape graphs (where every L touches the circle by it lowest and right-most points), are the same as the circle-segment graphs (or simply circle graphs) [START_REF] Jelínek | On grounded L-graphs and their relatives[END_REF].

• 2-grounded segments graphs, that is interval graphs, are included in grounded Lshape: simply use L's that all have the horizontal segments at the same altitude.

• Both grounded L-shape and grounded rectangles are included in in C ab by Observation 1. As these two classes are not comparable [START_REF] Jelínek | On grounded L-graphs and their relatives[END_REF], these inclusions are strict.

Stairs

Class. For stairs, only the 2-grounded case has been considered. The 2-grounded stairs graphs are exactly the cocomparability graphs. Indeed, it is known that cocomparability graphs are intersection graphs of continuous functions between two lines (see [START_REF] Charles Golumbic | Comparability graphs and intersection graphs[END_REF] or the explanation we give in Subsection 4.8), and we can make these functions strictly increasing, and them discretize them to get stairs. Comparability graphs are characterized by the pattern of Figure 12. Inclusions In several settings stairs generalize segments. First suppose that the segments are pointing upward to the right. Then one can transform those into stairs: just discretize the segments into stairs, with a fine enough discretization to keep the same intersections. As a matter of fact, we can often assume that the segments are pointing to the right: if it is not the case, we can tilt all the segments to the right, until they are all pointing to the right. This techniques works for example for 2-grounded stairs, that are included into 2grounded segments (which is not a surprise as these classes boil down to permutation and cocomparability graphs). It also allows to prove the following observation, that we use in Figure 4.

Observation 9. Grounded segment graphs are contained in grounded stairs graphs.

Convex Polygons

Circle-polygon graphs were studied in [START_REF] Alexandr | Covering and coloring polygon-circle graphs[END_REF]. Grounded convex polygons contain grounded segments and grounded rectangles by Observation 8.

Strings

Classes Grounded string graphs are the same as outer-string graphs (by Observations 7 and 4, as noticed in [START_REF] Cardinal | Intersection graphs of rays and grounded segments[END_REF]). Outerstring graphs are well studied. See Figure 13a for a grounded representation of such a graph.

The 2-grounded string graphs are co-comparability graphs [START_REF] Charles Golumbic | Comparability graphs and intersection graphs[END_REF]. Let us give some detail on this topic. Any shape between 2 lines separates the vertices (or shapes) in between two lines as left part and right part (shapes totally to the left or totally to the right). Therefore the relation : being totally to the left (resp. the right) is a partial order and therefore its complement is a comparability graph. This implies that every 2-grounded class is included in cocomparablity graphs, and for 2-grounded string graphs this is an equality.

Bigrounded string graphs are known as interval filament graphs [START_REF] Fanica | Maximum weight independent sets and cliques in intersection graphs of filaments[END_REF]. See Figure 13b for a representation.

Inclusions

• It was shown in [START_REF] Fanica | Maximum weight independent sets and cliques in intersection graphs of filaments[END_REF] that bigrounded string graphs contain 2-grounded string graphs (by what we called Observation 6), and circle-polygon graphs, and that these inclusions are strict.

• Outer-segment are strictly included in outer-string [START_REF] Cabello | Refining the hierarchies of classes of geometric intersection graphs[END_REF].

• Strings generalize all the shapes we use. This is clear for segments, stairs and L-shape which are special strings, but it is also true for rectangles and convex polygons, as their boundaries are strings, and only the boundary matters for intersections.

Touching grounded intersection characterization

Theorem 1. The touching grounded L-shape graphs are the forests.

Note that forests are also characterized by a pattern on three vertices (See Table 1).

outerstring-eps-converted-to.pdf Proof. Before we prove both inclusions, let us introduce a notation and make an observation. First, a grounded L-shape S can be characterized by three numbers:

1. The abscissa of its rooting point, that we denote x(S).

2. The abscissa of its right-most point, that we denote x (S).

3. The ordinate of it horizontal segment, that we denote y(S).

When S corresponds to a vertex v in a graph, we will abuse notation, and write x(v), x (v) and y(v). Now, in a touching L-shape representation, two L-shapes S and S , with x(S) < x(S ) can touch in only one way: S touches the vertical part of of S , with its right-most point.

Remember that forests are characterized by the pattern on three nodes with edges (1, 2) and (1, 3) (see Table 1). Now, consider the grounding order of an arbitrary set of touching grounded L-shapes. Take three shapes S 1 , S 2 and S 3 in that order. If S 1 and S 2 are touching, then this has to be on the right-most point of S 1 , and on the vertical part of S 2 . Then S 1 cannot go further right than the grounding position of S 2 , because then it would cross S 2 . (Remember that for string-like shapes, we defined "touching" as "touching even if we were to make the strings have non-zero thickness", thus crossings are forbidden for touching L-shapes.) Consequently, S 1 cannot reach S 3 . Therefore, the grounding ordering of the shapes avoids the forbidden pattern of forests, and touching grounded L-shape graphs are included in forests.

For the other direction, we build a touching L-shape representation for any forest. First, note that we can assume without loss of generality that the forest is actually a tree T , because the representations of the different connected component can be placed side by side on the line.

Our construction is top-down, that is, we place the L-shape of the root first, and we go down in the tree towards the leaves. Consider the tree T of the vertices that have been added so far to the drawing. At first T is empty, and at the end T = T . Our construction will take place in the unit square [0, 1] × [0, 1]. We first represent the root r as a vertical segment between positions (1, 0) and (1, 1). At that point T = {r}. We explain how we can take a leaf from T , and add all its children in T to T , by adding them to the drawing. By induction, this describes a touching L-shape representation of the tree.

We maintain the following invariant. For any vertex v that is a leaf in T , there exists an abscissa x * (v) < x(v), and an ordinate y * (v) ≤ y(v), such that the rectangle (x * (v), x(v)) × [0, y * (v)] intersects none of the shapes placed so far. Note that this invariant is satisfied when we have just the root in T , with x * (v) = 0 and y * (v) = 1. Suppose, the invariant holds for an arbitrary leaf v of T . Now, consider the children of v in T : v 1 , . . . , v k (in an arbitrary order). For each v i , we build the L-shape with the following characteristics (see Fig. 14): One can check that these shapes do not intersect, and that they all touch the shape of v. Also, because they are in the rectangle of our invariant, they touch no other shape. Finally, our invariant is preserved, since for any new leaf v i , the rectangle with the following coordinates is empty: x * (v 1 ) = x * (v) and x * (v i ) = x(v i-1 ) for i > 0, and y * (v i ) = y(v i ), for all i.

x(v i ) = x * (v) + i • x(v) -x * (v) k + 1 x (v i ) = x(v) y(v i ) = (k -i + 1) • y * (v) k + 1 . x * (v) x(v 1 ) x(v 2 ) x(v 3 ) y * (v) y(v 1 ) y(v 2 ) y(v 3 ) x(v )
Theorem 2. The touching grounded strings graphs are the outerplanar graphs.

As already mentioned outerplanar graphs are also characterized by the pattern P ∅ .

Proof. Consider an outerplanar graph, and let us build a representation by touching rectangles (which are a special case of touching strings). For a point p of the grounding line, let its left diagonal be the half-infinite line that starts at p, and goes in the north-west direction. Similarly define the right diagonal for the north-east direction. Consider an ordering of the vertices of the graph that avoids the pattern P ∅ . Plant the corresponding rectangles regularly on the line in this ordering. For a given vertex v, let v and v r its left-most and right-most neighbors in the ordering (considering that v is a neighbor to itself). Now the rectangle of v is defined in the following way:

• Its left-most corner is at the intersection of its left diagonal and of the right diagonal of v .

• Its right-most corner is at the intersection of its right diagonal and of the left diagonal of v r .

Clearly, this intersection graph will have all the intersection of the original graph. Let us prove that there are no other intersection. Suppose there is an intersection between the rectangles of vertices a and b, with a < b, but a and b are not neighbors in the graph. Then, by construction it must be that a has a neighbor c such that b < c, and b has a neighbor d such that d < a. Consequently, the nodes d < a < b < c form P ∅ , the forbidden pattern of outerplanar graphs, which is a contradiction.

In the other direction: suppose we have a touching string representation, let us prove that the ordering of the shapes along the line corresponds to an ordering of the vertices that avoids the pattern. For the sake of contradiction, suppose we have four strings a, b, c and d, such that a and c are in contact, and b and d are in contact. Strings a and c must touch at some position p. Now the grounding point of b is in the region delimited by the grounding line and the parts of a and c that starts on the grounding line and end in p. The grounding point of d is outside this region, and none of b or d can cross the boundaries of the region, thus b and d cannot meet, a contradiction.

We can derive from the proof that outerplanar graphs also correspond to touching grounded rectangle graphs, and touching grounded polygon graphs.

Interval filament graphs are between C a and C ab

In this section, we prove that the geometric class of interval filament graphs is between the pattern classes C a and C ab . We think that it is insightful to have both inclusions into one theorem, but for convenience, we split the theorem into two lemmas for the proofs. Proof. Consider an interval filament representation. We claim the order of the left grounding points of the interval filaments avoids the pattern P ab . For the sake of contradiction, suppose that the pattern appears in this ordering, on some vertices a < b < c < d. Let α a , α b , α c , α d be the left endpoints, and β a , β b , β c , β d be the right endpoints of the filaments corresponding to a, b, c and d. Because b and d are adjacent, it must be that α d < β b . Similarly, because a and c are adjacent, α c < β a . Since a and b are not adjacent, we cannot have α a < α b < β a < β b , therefore, given the inclusions above, we must have α a < α b < α c < α d < β b < β a . Consequently, α c is in the region of the plane delimited by the grounding line and the filament of b. As c is not adjacent to b, it cannot reach the filament of a (whose extremities are outside the interval of b), which is a contradiction.

We move on to the second inclusion.

Lemma 2. C a ⊆ Interval filaments.

Proof. Consider a graph G in C a . We show how to compute a proper interval filament representation of G. To do so, we first create a set of interval filaments that is not a proper representation of G in general, and then modify it several times, until it becomes a proper intersection representation of G. The outcome of our construction is illustrated on an example in Figure 15. Figure 15: On the top picture, a graph whose vertices are ordered to avoid P a . On the bottom picture, the interval filament representation built by our construction. (A few modifications of the construction have been used for readability, including using a smaller scale on the vertical axis than on the horizontal axis.)

We start with a first representation that we call R 1 . Consider an order of the vertices of G avoiding P a . We will abuse notation and write u instead of "the rank of u in the ordering". For every the vertex u, we denote its right-most neighbor by r u (with r u = u when u has no neighbor on the right). Let ε u = n-u+1 n+1 . We note that for two vertices u < v, 0 < ε v < ε u < 1. In R 1 , the filament of u starts at position (u, 0), goes up to point (u, r u -u + ε u ), then goes right to the position (r u + ε u , r u -u + ε u ), and then goes down to the grounding line at (r u + ε u , 0). Note that at this point each filament forms a square with the grounding line. For further reference, we denote the altitude of horizontal segment as h u = r u -u + ε u .

Claim 1. In R 1 , all the intersections between filaments correspond to edges in the graph, and at any intersection point, there are exactly two filaments intersecting, one that is locally vertical and one that is locally horizontal.

Proof of the claim. Let us start by proving the first part of the claim. Consider the filaments of two vertices u < v. We make a case analysis depending on the placement of r u and r v .

• If u ≤ r u < v ≤ r v , then the two filaments do not intersect.

• If u < v ≤ r v ≤ r u ,
then again the filaments do not intersect. Indeed, the square corresponding to v, starts at position v (> u) and stops at r v + ε v (< r u + ε u ), thus is fully included into the square of u.

• If u < v < r u < r v , then the filaments intersect in R 1 , but in this case, since by definition (u, r u ) and (v, r v ) are edges in G, either (u, v) is an edge in G, or we get that u < v < r u < r v form a P a in the ordering, which is a contradiction. Now, for the rest of the claim, note that any horizontal segment is at an altitude of the form k + ε u , where k is an integer, and ε u ∈ (0, 1) is specific to the node u where the filament starts. Thus, no two horizontal parts of two different filaments can intersect. The analogue reasoning holds for the vertical parts. The claim follows.

In general, R 1 is not a proper representation of G, because there are edges in the graphs that do not correspond to filament intersections. We now modify this first representation R 1 into a second representation R 2 .

For a vertex v, we select (when it exists) the vertex w such that:

• w is on the left to v,

• w is adjacent to v in G,

• the filaments of w and v do not intersect in R 1

• among the vertices satisfying the three points above, w is the one that has the highest horizontal segment (that is, the largest h w ).

We modify the shape of v with a spike at the beginning: the first vertical line goes up to h w , and then goes down to h v , and continues the shape as before. (If we want the filament to not self-intersect, we can go down with some steep enough slope, like in Figure 15.) Claim 2. For every edge of the graph, there is an intersection of filaments in R 2 . Moreover, if the filaments corresponding to some vertices y < v intersect in R 2 , and y and v are not adjacent in G, then there must exist a vertex x, with x < v, such that (x, v) ∈ G and h y < h x .

Proof of the claim. First, note that all filaments intersections from R 1 also appear in R 2 . Also, note that the spikes appear on different zones of x-axis, thus they do not interfere. Now, consider a pair of nodes v < u, such that (v, u) ∈ G, but the two corresponding filaments were not intersecting in R 1 . By definition of r v , u ≤ r v , thus v < u < r v + ε v . Therefore, in R 1 the horizontal part of the filament of v goes above the left grounding point of u. The vertex u satisfies the three first conditions of the vertex w defined above, and because h w is chosen to be maximal, we get that the spike of u necessarily touches the filament of v. Thus the intersection between the filaments of v and u appears in R 2 , which proves the first part of the claim. Now, if there is an unwanted intersection, that is an intersection in R 2 that does not appear in G, it must be because of a spike of some vertex v, that intersects the horizontal part of the filament of a vertex y with (v, y) / ∈ E, while going up to touch u. This can only happen if the conditions of the claim are satisfied.

We now define R 3 , which will be our final filament representation. Let us first define an ε-chimney. Consider a horizontal segment [(x 1 , y), (x 2 , y)] and a vertical segment [(x, y 1 ), (x, y 2 )] that intersect at position (x, y). Then an ε-chimney is a modification of the horizontal segment, to avoid the vertical segment. More precisely, it is the piece-wise segment going through the following points: (x 1 , y), (x -ε, y), (x -ε, y 2 + ε), (x + ε, y 2 + ε), (x + ε, y), (x 2 , y).

Let us call a conflict an intersection between two filaments that does not correspond to an edge in G. As mentioned earlier, a conflict is necessarily between the spike of a filament and the horizontal plateau of another filament. For any given filament u, we show how to solve all the conflicts that involve the spike of u, without loosing the intersection that are needed in G. We do so by only modifying the filaments in a small vertical column around the abscissa of u. We will maintain the invariant that when we consider a filament v, every filament w above it has been treated: either (u, w) ∈ E and the intersection has been preserved, or (u, w) / ∈ E and the intersection has been removed. We consider the filaments that intersect the spike of u ordered by the altitude of their horizontal plateaus, from the highest to the lowest. For each such filament v, we do the following:

• If (u, v) ∈ E, do nothing. • If (u, v) / ∈ E:
-If there is a filament w above v, such that (v, w) / ∈ E, and w intersects the spike of u, then we claim that there is a contradiction. Indeed, if (v, w) is not in G, and h v < h w , necessarily, w < v < u < r v < r w . Then w < v < u < r v is an occurrence of P a , because (w, v) / ∈ E (by hypothesis), (w, u) ∈ E (by the invariant) and (v, r v ) ∈ E (by definition).

-If there is no filament w above v, such that (v, w) / ∈ E, and w intersects the spike of u, then we transform the filament of v, by building a chimney around the spike of u. The ε of this chimney is taken to be smaller than all the ε used for chimneys of filaments modified so far around the spike of u. If this is the first chimney, then we take ε to be the minimum between 1/4, and the space between the top of the spike of u and the next plateau above (if it exists).

We claim that this construction gives a proper interval filament representation of G. First note that, the conflict resolution is independent at all vertices, because the chimney we build are taken with a sufficiently small ε around the spikes. Hence, it is sufficient to show for each spike that: we have not lost correct intersections, we have removed all the incorrect intersections, and have not created new ones.

The correct intersections that were present in R 2 are of two types: the ones coming from R 1 and the ones between a spike and horizontal plateaus. We have only modified the graphs around the spikes, thus the first type is safe. Moreover, when we had an intersection corresponding to an edge (u, v) ∈ E, we have not modified the filament, hence the second type is also safe.

All the incorrect intersections at some given spike in R 2 have been removed thanks to our chimney constructions.

Finally, we have not created any new intersection. Indeed, while building a chimney, the only new incorrect intersection that we might have created is with another chimney, but this cannot happen as we have taken care of reducing the ε parameter at every chimney. The main part of this theorem is the first inclusion. The second inclusion can actually be derived from a result in [START_REF] Pach | On the chromatic number of disjointness graphs of curves[END_REF]. More precisely, in [START_REF] Pach | On the chromatic number of disjointness graphs of curves[END_REF] it is proved that the disjointness graph of x-monotone curves are semi-comparability graphs. This is related to our result because: the disjointness graph is the complement of the intersection graph, x-monotone graphs are a generalization of grounded stairs graphs, and semi-comparability are the graphs that avoid the complement of C abc .

Proof. Let us start with the first inclusion, and consider a graph G = (V, E) in C ab . We build a grounded stairs representation incrementally, by adding the stairs one by one, from left to right, in the ordering of G avoiding the pattern P a,b . Actually, for every new vertex i, allow ourselves to modify the stairs 1 to i -1, such that at the end of the process, the adjacency of the vertices 1 to i in the graph is the same as the one in the grounded stairs configuration.

For any new vertex i, we create an infinite vertical line, grounded at position i. We will cut the line into a finite segment at the end of this step of the construction, and maintain the invariant that all the stairs are finite. We will maintain the invariant that the representation of vertices 1 to k only uses abscissas in [1, k], thus, at that point, the line has no intersection. Consider a stair j, with j < i in the ordering, and such that (i, j) ∈ E. We claim that it is possible to modify the stairs of j, so that they intersect the segment of i, without creating an unwanted intersection with the stairs of any vertex k, with (j, k) / ∈ E. Note that proving that we can make the stairs of j and i intersect simply means that we can extend the stairs of j beyond the abscissa i.

For the sake of contradiction, suppose there are some stairs j, such that the extension to i is no possible. It means that there is a position x on the horizontal axis, such that the stair j cannot be extended beyond abscissa x. We extend the stairs j to a position p = (x -ε, t) for a small ε. Now, as by invariant, all the stairs of index smaller than i are finite, there must be an ordinate y, such that if we make stairs j go up from p, it cannot go further than y. (If such an ordinate y would not exist, then we could just go high enough to be above all the stairs except i, and then go straight to i, which would contradict that fact that we cannot go beyond abscissa x.)

In this situation, the position (x, y) must be the intersection of two stairs and r, having an horizontal segment at height y , and r having a vertical segment at abscissa x. And necessarily and r are not adjacent to j in G. We claim that in the ordering, < j < r < i. Indeed, i has the right-most stairs by definition, and given the configuration described above, any other ordering would imply an intersection between the stairs or r, and the stairs of j. Then, the vertices < j < r < i correspond the pattern P a,b because we have edges ( , r) and (j, i), and non-edges ( , j) and (j, r). This is a contradiction. Therefore, we can always extend the stairs of j to the stairs of i, and get the same adjacency in the representation and in the graph for vertices from 1 to i. Finally, we cut the infinite vertical line of i just above its last intersection to make it a finite segment. This finishes the proof of the first inclusion.

Let us now prove that grounded stairs graphs are included in C abc . Consider a grounded stairs representation. We claim that the grounding ordering of the associated graph avoids the pattern P abc . Suppose that it is not the case, and that the pattern appears on some vertices a < b < c < d. Consider the zone of the plane between the grounding line, the stairs of a, and the stairs of c, below their (first) intersection, whose coordinates will be denoted (x, y). This zone contains the grounding point of b. Because intersections between the stairs of b and the stairs of a and c are forbidden, the stairs of b are fully contained in this zone. Now, the stairs of d must appear strictly on the right of the stairs of c until ordinate y, because these two do not intersect either. Finally, the rest of the stairs of d is in the quarter of the plane that is on the top right of (x, y). For both parts of the stairs of d, the intersection with the stairs of b is impossible. This is a contradiction, and proves the inclusion.

Inclusions of grounded convex and string

In this section, we show two easy inclusions of geometric classes into pattern classes.

Theorem 5. Grounded convex graphs are included in C abc .

Proof. Consider the grounded convex representation, and suppose that the pattern of C abc is present with vertices a < b < c < d, when considering the graph in the grounding ordering. Note first that the intersection of the convex shapes a and c is itself a convex shape. Let P be a lowest point of this convex intersection. By similar arguments as in the previous section, the ordinate of P is the highest ordinate that the shape of b can reach. Now, as the shape d must avoid the shape c, it must in particular pass "above" the segment between P and the grounding point of c. Therefore b and d can only touch at P , and this is impossible as we required that there cannot be a contact of more than two shapes on each point (except for interval graphs). This is contradiction, it proves the theorem. Theorem 6. Grounded string graphs are included in C abcd .

This statement was already proved in [START_REF] Pach | Ordered graphs and large bi-cliques in intersection graphs of curves[END_REF], and it corresponds to the proof sketch we gave in Section 2. We reprove it here formally for completeness.

Proof. We again reason by contradiction, and consider the grounding ordering in a representation by grounded strings. Suppose we have four vertices a < b < c < d, such that the only edges between these vertices are (a, c) and (b, d). Then, consider the closed region of the plane that is inside the Jordan curve defined by the string of a, the string of c, and the grounding line. The shape b must be inside this region because its root is, and it cannot intersect any of the boundaries, by Jordan curve theorem. On the other end d must be outside this region, because likewise its root is outside and it cannot cross the curve. Then b and d cannot intersect, which is a contradiction.

Note that another way to see Theorem 6 is that the complement of grounded string graphs avoids the complement of P abcd , which is an induced cycle in the natural order. This is actually not very surprising, as it is known that the class of complement of triangle-free intersection graphs of grounded curves is exactly the class of Hasse diagrams [START_REF] Middendorf | Weakly transitive orientations, hasse diagrams and string graphs[END_REF], and that even without the triangle-free assumption, these complement graphs avoid an infinite family of ordered cycles [START_REF] Frank W Sinden | Topology of thin film rc circuits[END_REF].

Strict inclusions and open problems

In this section, we focus on inequalities between included classes, and open problems. In particular, we finish giving the results that are used to establish the diagram of Figure 4, given in the overview section of the paper.

We start with new inequalities between pattern classes. Remember that inclusion of patterns imply inclusion of classes (Observation 1), thus we have the following inclusions: A natural open problem here is whether all the inclusions are strict, and even more generally, the following question.

C ∅ ⊆ C a ⊆ C ab ⊆ C abc ⊆ C abcd ⊆ ALL,
Open problem 1. Let P be a pattern with a non-decided edge (x, y). Let P be the pattern obtained from P by adding the edge (x, y). Under which conditions does C P C P hold? What about adding a non-edge (x, y)?

We now give a list of inequalities between classes, that are either known, or easy to derive from known results. Observation 11.

1. Grounded L-shape graphs are strictly included in grounded segment graphs [START_REF] Middendorf | The max clique problem in classes of string-graphs[END_REF].

2. Grounded L-shape graphs and grounded rectangle graphs are incomparable [START_REF] Jelínek | On grounded L-graphs and their relatives[END_REF].

This result has several consequences. First the inclusions of grounded rectangle graphs grounded L-shape graphs into C ab (which follow from the pattern inclusions) are strict. Second, the inclusion of grounded rectangle graphs into grounded convex graphs (which follows from the comparison of the shapes) is also strict.

3. Grounded rectangle graphs and grounded segment graphs are incomparable [START_REF] Jelínek | On grounded L-graphs and their relatives[END_REF]. As a consequence, the inclusion of grounded segment graphs into grounded convex graphs (which follows from the comparison of the shapes) is strict.

4. We know from the literature (or alternatively from Theorem 1 and 2) that forest are included in outerplanar graphs. This inclusion is strict as witnessed by the cycle on four vertices, C 4 , that is outerplanar but not acyclic.

5.

By Theorem 1, we get that forests are included in grounded L-shape graphs. This inclusion is strict, as witnessed by C 4 again (Figure 11a shows that C 4 is a grounded L-shape graph).

6. Interval graphs are included in C a , cocomparability graphs, grounded rectangle graphs, and grounded L-shape, as can be seen from the pattern inclusions (for the first three class) and from the generality of the shapes and grounding (for the fourth). These inclusions are strict as witnessed by C 4 again.

7. The class of 2-grounded segments graphs (permutation graphs) is strictly included in the classes of grounded L-shapes and grounded segments [START_REF] Jelínek | On grounded L-graphs and their relatives[END_REF].

8. Cocomparability graphs are included in interval filament graphs, by Observation 6, and the inclusion is strict, as witnessed by C 6 which is not a cocomparability graph [START_REF] Gallai | Transitiv orientierbare graphen[END_REF] and can be easily represented by interval filaments.

Now that we have all the results that are used to build the Diagram of Figure 4, we can list some open problems. Of course settling the status of each inclusion (either equality or strict inclusion) is a natural direction. For example, the lowest such edge in the diagram is for the inclusion of C a in interval filament graphs. This question would be solved if could answer positively the following, innocent-looking problem.

Open problem 2. Are C a and cocomparability graphs incomparable? (Or are cocomparability graphs included in C a , the reverse being impossible, as witnessed by C 6 ?)

We know that C ∅ is the class of outerplanar graphs, and that C b is the class of grounded rectangle graphs, which gives us several points of view on these two classes defined by forbidden patterns. We lack such diversity for other the other pattern classes considered in the paper.

Complexity of recognition

As said in the introduction, one of the motivations to study the relation between patterns and grounded intersection graphs is that it is a way to better understand patterns on four vertices. In this section, we survey the known results and list open problems about the complexity of the recognition of the classes that are defined by patterns on four vertices.

Let us start by classes that are known to be recognizable in polynomial time. Remember that all the classes characterized by patterns on three vertices can be recognized in polynomial time [START_REF] Hell | Ordering without forbidden patterns[END_REF][START_REF] Feuilloley | Graph classes and forbidden patterns on three vertices[END_REF]. When we go to four vertices, the landscape is more complex, but there are still "good cases".

First, outerplanar graphs, that have been mentioned a lot already, as they correspond to C ∅ , can be recognized in linear time [START_REF] Mitchell | Linear algorithms to recognize outerplanar and maximal outerplanar graphs[END_REF]. Second, let us consider the class of cographs, which is the smallest class of graphs that contains the unique vertex graph and is closed under series and parallel compositions. The cographs are also the P 4free graphs [START_REF] Seinsche | On a property of a clas of n-colorable graphs[END_REF], hence they can be characterized by the existence of a vertex ordering avoiding the twelve orderings of P 4 . But there is a more compact set of forbidden patterns [START_REF] Damaschke | Forbidden ordered subgraphs[END_REF], see Fig. 18. The cographs can also be recognized in linear time [START_REF] Corneil | A linear recognition algorithm for cographs[END_REF].

A less-known class is the strongly chordal graphs in which every even cycle of length greater or equal to 6 admits an odd chord. These are characterized by the existence of a strong perfect elimination ordering of the vertices, which corresponds to the patterns of Figure 19 [START_REF] Farber | Characterizations of strongly chordal graphs[END_REF]. They can be recognized in time O(min(n 2 , (n + m) log n)) [START_REF] Spinrad | Doubly lexical ordering of dense 0-1 matrices[END_REF]. The complement of threshold tolerance graphs (coTT for short) is surclass of the strongly chordal graphs that have been characterized with the patterns of Figure 20 [START_REF] Monma | Threshold tolerance graphs[END_REF], and whose recognition is also polynomial [START_REF] Golovach | On recognition of threshold tolerance graphs and their complements[END_REF]. Finally, note that K 4 -free graphs (resp. their complement) are characterized by the pattern that is an ordered version of K 4 (resp. of K4 ). These can be recognized in time O(m α+1 2 ), where α is the best exponent for boolean matrix multiplication [START_REF] Kloks | Finding and counting small induced subgraphs efficiently[END_REF]. As hinted before, there are also classes that are characterized by patterns on four vertices and that are hard to recognize. The simplest example of this phenomenon is 3-colorable graphs, whose recognition is a classic NP-hard problem. These are characterized by the forbidden pattern that is simply a path on four vertices (see e.g. [START_REF] Feuilloley | Graph classes and forbidden patterns on three vertices[END_REF], but this is also a special case of the Gallai-Hasse-Roy-Vitaver theorem).

Another example is the class of graphs with queue number 1, that can be characterized with the pattern of Figure 21 [START_REF] Heath | Comparing queues and stacks as mechanisms for laying out graphs[END_REF], and whose recognition is NP-hard [START_REF] Heath | Laying out graphs using queues[END_REF]. One more example is perfectly orderable graphs, that are the graphs that admit a perfect ordering of the vertices, i.e. an ordering where there is no path on four vertices (a -b -c -d), such that a < b and d < c. These are characterized by the forbidden patterns of Figure 22, and their recognition was proven to be NP-hard in [START_REF] Middendorf | On the complexity of recognizing perfectly orderable graphs[END_REF]. Let us now move on to the interesting classes for which we do not know the complexity of the recognition. First, the recognition complexity of almost all the pattern classes on Figure 4 is unknown. In particular, the question for grounded rectangle graphs, that is C b , is still open, although it has been raised several time in the literature. A related class of interest is the one where the pattern has edges (1, 3), [START_REF] Cardinal | Intersection graphs of rays and grounded segments[END_REF][START_REF] Catanzaro | Max point-tolerance graphs[END_REF] and [START_REF] Cardinal | Intersection graphs of rays and grounded segments[END_REF][START_REF] Corneil | Extensions of permutation and interval graphs[END_REF]. This pattern correspond to P b but with an edge instead of a non-edge, and it is also a permutation of the pattern for 3-colorable graph. To our knowledge this class has not received attention yet.

We will finish this section with graph classes related to two parameters: the LMIMwidth and the MIM-width. These are interesting parameters based on the size of some maximum matchings, that are related to the other classic parameters such as treewidth, branchwidth, rankwidth and cutwidth [START_REF] Vatshelle | New width parameters of graphs[END_REF][START_REF] Kang | A width parameter useful for chordal and co-comparability graphs[END_REF]. The graph of LMIM-width 1 are known to be characterized by the two patterns of Figure 23, including P abcd . The graphs that have MIM-width 1 correspond to linear Hsu-decomposable graphs, and they can be characterized by the two forbidden patterns of Figure 24 [START_REF] Vatshelle | New width parameters of graphs[END_REF][START_REF] Kang | A width parameter useful for chordal and co-comparability graphs[END_REF].

As far as we know the complexity of the recognition of LMIM-width 1 and MIMwidth 1 are still widely open. Figure 24: The patterns characterizing the graphs of MIM-width 1. The first pattern is P bd .

Conclusion

In this paper we prove that forbidden patterns can help to better understand the relationships between graph classes, but it is no clear how they could help for the classification of the complexity of the recognition of the corresponding graph classes. Since very similar patterns may lead to either linear (such as C ∅ ) or perhaps NP-hard recognition algorithms (such as C b ).

  (a) Grounded rectangles.

Figure 2 :

 2 Figure 2: Grounded rectangle graphs and their forbidden pattern on 4 vertices.

Figure 3 :

 3 Figure 3: A grounded intersection model and a related pattern on four nodes.

Figure 4 :

 4 Figure 4: Diagram of our results. The name of the classes in our vocabulary are written in normal font, the names in the literature are written in italic font. Edges represent inclusions. Thick edges are known strict inclusions. G. stands for grounded, T-G stands for touching grounded, B-G. stands for Bigrounded, and 2-G. stands for 2-grounded.

Figure 5 :Remark 1 .

 51 Figure 5: Illustration of P abcd (Definition 4).

Figure 6 :

 6 Figure 6: Grounding types of Definition 6.

Figure 7 :

 7 Figure 7: Illustration of Observation 4 with grounded-polygons and outer-polygons.

Figure 8 :

 8 Figure 8: Illustration of Observation 5 with 2-grounded-polygons and circle-polygons.

Figure 9 :

 9 Figure 9: Illustration of Observation 6 with 2-grounded strings and bigrounded strings.

Figure 10 :

 10 Figure 10: Two characterizations of permutation graphs.

  (a) Grounded L-shapes and the associated grounded-L graph.

Figure 11 :

 11 Figure 11: Definition and pattern characterizations of grounded L-graphs.

Figure 12 :

 12 Figure 12: Two characterizations of cocomparability graphs.

  (a) An outer-string representation and graph. filament-eps-converted-to.pdf (b) An interval filament representation and graph.

Figure 13 :

 13 Figure 13: Representations of an outer-string graph and an interval filament graph.

Figure 14 :

 14 Figure 14: Illustration of the construction of the proof of Theorem 1..

Theorem 3 .

 3 The following holds: C a ⊆ Interval filaments ⊆ C ab .

Lemma 1 .

 1 Interval filaments ⊆ C ab .

7

  Grounded stairs graphs between C ab and C abc Theorem 4. The following holds: C ab ⊆ grounded stairs ⊆ C abc .

Open problem 3 .

 3 Can we characterize C a,b , C a,b,c and C a,b,c,d , without patterns? Do these classes have geometric characterizations?

Figure 18 :

 18 Figure 18: Forbidden patterns of cographs.

Figure 19 :

 19 Figure 19: Forbidden patterns of strongly chordal graphs.

Figure 20 :

 20 Figure 20: Forbidden patterns of coTT graphs.

Figure 21 :

 21 Figure 21: Forbidden pattern of the graphs of queue number 1.

Figure 22 :

 22 Figure 22: Forbidden patterns of perfectly orderable graphs.

Figure 23 :

 23 Figure 23: The patterns characterizing the graphs of LMIM-width 1. The first pattern is P abcd .

Table 1 :

 1 The table from

	Graph Class	Forbidden Pattern
	Linear forests
	Stars
	Interval graphs
	Split graphs
	Forest
	Bipartite graphs
	Chordal graphs
	Comparability graphs
	Triangle-free graphs
	At most two nodes

  where ALL stands for the set of all graphs. Also C ∅ ⊆ C b ⊆ C ab .Two inclusions are known to be strict: Observation 10. The class C ∅ , is strictly included into C a and C b . For example K 4 has no ordering avoiding P ∅ , but all orderings avoid P a and P b . We prove three other inequalities between included classes. Theorem 7. C a C ab , C b C ab , and C abcd ALL Proof. The proof of this theorem uses a computer program for enumerating vertex orderings. The source code is available upon request. For the first two inequalities, C a C ab and C b C ab , we consider the graph of Figure16. This graph is in C ab , as the second pictures shows, and a computer enumeration shows that it is not in C a , nor in C b . Two vertex ordering of a graph that is in C ab , but not in C a , nor in C b . The first pictures illustrates how we discovered this graph: taking P ∅ and then forcing some order conditions with intermediate nodes and a cycle. The second picture is an ordering avoiding P ab . (We made some edges thicker to increase readability.)For the third inequality, C abcd ALL, we consider the graph of Figure17. Again a computer enumeration shows that no vertex ordering of this graph avoids the pattern P abcd , thus the graph is not in C abcd .

	0 0 2 Figure 17: A graph that is not in C abcd , by computer enumeration. (We made some 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 3 4 5 6 7 8 9 10 11 Figure 16: 0 edges thicker to increase readability.)

Acknowledgments. The authors thank Istvan Tomon for pointing out to references [37], [38], [33] and [41].


À Eva Tamburro, merci pour tous ces matchs dignes de Roland Garros et pour tes cris qui font fuir tous les pigeons de la Jalade. Après presque 10 ans, il était temps de s'y mettre ! À Nicolas Boulet, merci de garder ce grain de folie à chaque soirée, de rebondir sur tout ce qu'on dit tel le Laurent Baffie de l'Anesthésie-Réanimation, d'être aussi bon dans ce que tu fais et aussi simple dans la manière avec laquelle tu le fais. Merci pour ce rire mythique et constant, qui nous fait dire qu'on peut rire de tout avec toi.

À celles et ceux qui ont illuminé mon internat

  assesseur : Monsieur le Professeur Sa mir JABER 2 ème assesseur: Monsieur le Professeur Gérald CHANQUES 3 ème assesseur: Madame le Docteur Audrey DE JONG À Richard Bremond et Alice Frau, merci pour toutes ces soirées (et ces afters…), pour tes consult' ophtalmo Richard, pour tes chorégraphies Alice. Hâte d'être en Septembre ! À Sabrina de Courville et Bruno Bongrand (et bientôt Noé), comment parler de vous sans parler … des légendaires soirées Harry Potter ? Merci pour tous ces moments et pour votre bonne ambiance permanente.

À

  ma promotion DESAR 2017 (la meilleure de toutes, disons-le) : À Nicolas Boulet, Thomas Sfara, Joris Pensier, Marine Papy, Benjamin Machelart, Pauline Willynck, Ambre Cuny, Thomas Lancry, Cléa Gandon, Boris Checkroud, Dimitri Ceausu, Yannis Biziou, Chloé Briane, Pierre-Baptiste Vialatte, Florène Airoldi, Eve Payan, Chloé Raimbert, Lili Merlhiot, Adrien Maudière et Hugo Loyer. On aura vraiment passé de belles années ensemble, surtout pendant les congrès de la SFAR. Les patients ont de la chance de vous avoir ! À la team des Biterrois : À Boris Monnin, Tayma Naciri, Olivier Bozon, Pierre-Baptiste Vialatte, Constant Guillot, Manon Brillu, Vassilis Wurtz-Gress, Lisa André, Marion Tabardel, Anaïs Jouffrey, Victoria Veldhuizen, Essia Joyez, Sarah Lavielle, Dorian Revessat, Claire Dumont, Arthur Sinet, Fabien Poy et Nuf-Nuf… Un 1 er semestre complètement déjanté. Improbable que l'ARS ait réuni les plus fous de la subdivision dans un même internat ! Résumé de l'étude Contexte : Plusieurs alertes liées au risque de mortalité et d'insuffisance rénale aiguë (IRA) ont été émises concernant les solutés de type hydroxyéthylamidons (HEA) chez le patient de soins critiques. Néanmoins, la place des HEA en chirurgie abdominale majeure est encore débattue. Cette méta-analyse avec analyse séquentielle d'essais a pour objectif de déterminer les effets d'une stratégie de remplissage vasculaire par HEA sur le risque d'IRA, de transfusion sanguine per opératoire et de complications intra abdominales postopératoires, en comparaison d'une stratégie de remplissage vasculaire par cristalloïdes. l\1éthode : Dans cette méta-analyse avec analyse séquentielle d'essais, nous avons recherché les essais contrôlés randomisés (ECRs) comparant une stratégie de remplissage vasculaire par HEA à une stratégie de remplissage vasculaire par cristalloïdes chez les patients ayant subi une chirurgie abdominale majeure. Le critère de jugement principal (CJP) était l'existence d'une IRA dans les 30 jours postopératoires, définie selon les critères KDIGO, en combinant les stades 1, 2 et 3 dans la catégorie IRA versus pas d'IRA (stade 0). Les critères de jugement secondaires (CJS) comprenaient le taux de transfusion sanguine per opératoire et le taux de complications intra-abdominales postopératoires. Nous avons utilisé le risque relatif (RR) avec intervalle de confiance à 95% pour la mesure du CJP (une P value< 0.05 était considérée comme statistiquement significative) et une correction de Bonferroni avec un intervalle de confiance à 99% pour la mesure des CJS (une P value< 0.01 était considérée comme statistiquement significative). Résultats : Sept ECRs réunissant 2 398 patients ont été inclus. Le remplissage vasculaire par HEA n'était pas associé à un risque plus élevé d'IRA à 130 (RR=l.22, 95%CI 0.94-1.59, p=0.13) comparativement au remplissage vasculaire par cristalloïdes. D'après l'analyse séquentielle d'essais, la puissance statistique de cette analyse était insuffisante pour pouvoir conclure avec un niveau de preuve élevé. Le remplissage vasculaire par HEA était associé à un taux plus élevé de transfusion sanguine per opératoire (RR=l.57 99%CI 1.10-2.25, p=0.001) et un taux similaire de complications intra abdominales postopératoires (RR=0.76 99%CI 0.57-1.02, p=0.02). Conclusion: Dans cette méta-analyse s'intéressant au remplissage vasculaire par HEA dans le cadre de la chirurgie abdominale majeure, le remplissage vasculaire par HEA n'était pas associé à un risque plus élevé d'IRA à 130 comparativement au remplissage vasculaire par cristalloïdes. Cependant, l'intervalle de confiance et l'analyse séquentielle d'essais ne permettent pas d'exclure formellement un effet délétère des HEA sur la fonction rénale. Mots clés : hydroxyéthylamidons, colloïdes, cristalloïdes, chirurgie abdominale, médecine péri opératoire.

Abstract

Background: In critically ill patients, wamings about a risk of death and acute kidney injury (AKI) with HES solutions has been raised. However, HES solutions may yet have a role to play in major abdominal surgery. This meta-analysis and trial-sequential-analysis (TSA) aimed to investigate the effect of HES intravascular volume replacement on the risk of AKI, intra operative blood transfusion and postoperative intra-abdominal complications compared to crystalloid intravascular volume replacement.

Methods:

In this meta-analysis and TSA, we searched for randomized controlled trials (RCTs) comparing intraoperative HES intravascular volume replacement to crystalloid intravascular volume replacement in adult patients undergoing major abdominal surgery. Primary outcome was 30-day AKI, defined as a binary outcome according to KDIGO criteria, combining Stages 1, 2, and 3 into an AKI category versus no AKI category (Stage 0). Secondary outcomes included rates of intra-operative blood transfusion and postoperative intra-abdominal complications. We used random effects models to calculate summary estimates. We used relative risk (RR) as summary measure for dichotomous outcomes, with corresponding 95% confidence intervals (CI) for the primary outcome (P-value < 0.05 was considered statistically significant) and 99% CI after Bonferroni correction for the secondary outcomes (P-value < 0.01 was considered statistically significant).

Results: Seven RCTs including 2,398 patients were included. HES intravascular volume replacement was not associated with an increased risk of 30-day AKI (RR=l .22,p=0.13), when compared to crystalloid intravascular volume replacement. According to TSA, this analysis was underpowered. HES intravascular volume replacement was associated with higher rates of blood transfusion (RR=l.57 99%CI 1.10-2.25, p=0.001), and similar rates of postoperative intra-abdominal complications (RR=0.76 99%CI 0.57-1.02, p=0.02).

Conclusions:

In this meta-analysis to focus on HES intravascular volume replacement in major abdominal surgery, HES intravascular volume replacement was not associated with a higher risk of 30-day AKI when compared to crystalloid intravascular volume replacement. However, confidence interval and TSA do not exclude harmful effects of HES intravascular volume replacement on the renal function.

Mots clés : Hydroxyethyl starch, colloid, crystalloid, abdominal surgery, perioperative care