J Bensmail

V Campos

A K Maia

N Nisse

A Silva

Deciding the Erdős-Pósa property in 3-connected digraphs ⋆

Keywords: Erdős-Pósa property, Planar digraphs, Butterfly minor

A (di)graph H has the Erdős-Pósa (EP) property for (butterfly) minors if there exists a function f : N → N such that, for any k ∈ N and any (di)graph G, either G contains at least k pairwise vertexdisjoint copies of H as (butterfly) minor, or there exists a subset T of at most f (k) vertices such that H is not a (butterfly) minor of G -T . It is a well known result of Robertson and Seymour that an undirected graph has the EP property if and only if it is planar. This result was transposed to digraphs by Amiri, Kawarabayashi, Kreutzer and Wollan, who proved that a strong digraph has the EP property for butterfly minors if, and only if, it is a butterfly minor of a cylindrical grid. Contrary to the undirected case where a graph is planar if, and only if, it is the minor of some grid, not all planar digraphs are butterfly minors of a cylindrical grid. In this work, we characterize the planar digraphs that have a butterfly model in a cylindrical grid. In particular, this leads to a linear-time algorithm that decides whether a weakly 3-connected strong digraph has the EP property.

Introduction

A classical result by Erdős and Pósa [START_REF] Erdős | On independent circuits contained in a graph[END_REF] states that there is a function f : N → N such that, for every k, every graph G contains either k pairwise vertexdisjoint cycles or a set T of at most f (k) vertices such that G -T is acyclic. The generalization of Erdős and Pósa's result for digraphs and directed cycles was conjectured by Younger [START_REF] Younger | Graphs with interlinked directed circuits[END_REF] and proved by Reed et al. [START_REF] Reed | Packing directed circuits[END_REF].

We say that H is a minor of G if H is obtained from a subgraph of G by a sequence of edge contractions. If H is a digraph and we restrict the contractions in the previous definition to butterfly contractions [START_REF] Johnson | Directed tree-width[END_REF], we get the definition of a butterfly minor. We say that a graph H has the Erdős-Pósa (EP) property for minors if there is a function f : N → N such that, for every k, every graph G contains either k pairwise vertex-disjoint copies of H as a minor or a set T of at most f (k) vertices such that H is not a minor of G -T . By changing graph into digraph and minor into butterfly minor, the previous definition can ⋆ The full versions of omitted or sketched proofs can be found in the appendix. be adapted into the EP property for butterfly minors in digraphs. In this view, if H is the undirected graph with a unique vertex and a unique loop on it and D is the digraph obtained from H by orienting its loop edge, then Erdős and Pósa proved that H has the EP property for minors while Reed et al. proved that D has the EP property for butterfly minors.

The results of Erdős and Pósa and Reed et al. were generalized by Robertson and Seymour [START_REF] Robertson | Graph minors v. excluding a planar graph[END_REF] for undirected graphs and by Amiri et al. [START_REF] Amiri | The Erdos-Pósa property for directed graphs[END_REF] for digraphs. Robertson and Seymour [START_REF] Robertson | Graph minors v. excluding a planar graph[END_REF] proved that an undirected graph G has the EP property for minors if, and only if, G is planar. Amiri et al. [START_REF] Amiri | The Erdos-Pósa property for directed graphs[END_REF] proved that a strong digraph D has the EP property for butterfly minors if, and only if, D is a butterfly minor of a cylindrical grid (see Figure 1). The results of Robertson and Seymour [START_REF] Robertson | Graph minors v. excluding a planar graph[END_REF] and Amiri et al. [START_REF] Amiri | The Erdos-Pósa property for directed graphs[END_REF] are similar since an undirected graph is planar if, and only if, it is a minor of some grid [START_REF] Robertson | Graph minors. vii. disjoint paths on a surface[END_REF]. Contrary to the undirected case, not all planar digraphs are butterfly minors of a cylindrical grid. In this paper, we provide a structural characterization of planar digraphs that are butterfly minors of a cylindrical grid. In particular, such characterization leads to a linear-time algorithm that decides whether a weakly 3-connected strong digraph has the EP property for butterfly minors.

Although planarity is a necessary condition for a digraph to be a butterfly minor of a cylindrical grid, it is not sufficient. For example, the two planar digraphs of Figure 2 are not butterfly minors of any cylindrical grid. To see this, first note that they are planar, weakly 3-connected, and have essentially a unique (up to the outerface) embedding in the plane, according to Whitney's Theorem [START_REF] Whitney | 2-isomorphic graphs[END_REF]. Note also that, in a cylindrical grid, any embedding is such that there is a point in the plane around which all directed cycles go, and in the same direction. We refer to this as being concentric and with same orientation. Now, in the digraph L of Figure 2, the matching between the two directed triangles forces that, in any planar embedding, either the two triangles are not concentric or they have opposite orientations. On the other hand, the digraph R of Figure 2 is acyclic but it is not a minor of any cylindrical grid. To see why, note that, if R was a butterfly minor of a cylindrical grid, then, because R is acyclic, it would also be a butterfly minor of a directed wall, which is the digraph obtained by cutting a cylindrical grid along "parallel" arcs (see Figure 1). Note that, in an embedding of a directed wall similar to the one given in Figure 1, no arc goes down. This means that some relative positions of the vertices of R in a directed wall are forced. Namely, the two sources v 4 and v 5 of R must be below each of their out-neighbors, vertex v 1 must be below its three out-neighbors, and the universal sink v 0 must be above every other vertex. It can then be checked that these positions must lead to some crossing arcs. This second example shows that sources and sinks may play an important role in the fact that a planar digraph may or may not be a butterfly minor of a cylindrical grid. In a way, our main result tells that the above two examples fully characterize the reasons why a planar digraph cannot be a butterfly minor of a cylindrical grid.

To formally state our main result, we need a few definitions. Given a digraph D = (V, A) and ∅ ̸ = X ⊂ V (D), the set of arcs between X and V \ X is denoted by (X, V \ X). We say that (X, V \ X) is a dicut if there are no arcs from V \ X to X. A dijoin path P of D is a directed path in D whose arc-set intersects the arc-set of every dicut of D. A plane digraph is a planar digraph together with a planar embedding. Recall also that, given a plane digraph H, H * denotes its dual. We can now state our main result. Theorem 1. A digraph D is a butterfly minor of a cylindrical grid if, and only if, D has a plane spanning supergraph H with neither sources nor sinks such that H * admits a dijoin path.

To get further intuition about Theorem 1, consider the definition of a feedback arc set F ⊆ A of a digraph D = (V, A), which is any subset of arcs such that D -F is acyclic. Given a plane digraph D, it is known that every directed cycle of D is associated to a dicut in D * . This implies that a set of arcs is a feedback arc set of D if, and only if, the corresponding set of its dual edges intersects the arc-set of every dicut of D * [START_REF] Bang-Jensen | Digraphs Theory, Algorithms and Applications[END_REF]. Therefore, the fact that D * admits a dijoin path means that such path intersects the arcs of a feedback arc set of D "in the same direction", i.e., intersects the drawing of each directed cycle of D, with each intersection occurring in the same orientation. This is equivalent to being concentric and with the same orientation. This condition (D * admits a dijoin path) allows avoiding the kind of planar digraphs as exemplified by the digraph L in Figure 2. In turn, the difficulties exemplified in digraph R in Figure 2 are dealt with by the existence of a supergraph H with neither sources nor sinks.

Structure of the paper and algorithmic applications. We first prove that if D is a plane digraph with neither sources nor sinks such that D * has a dijoin path, then D is a butterfly minor of a cylindrical grid (Theorem 4). Observe that this gives us the sufficiency part of Theorem 1. We then show that if D is a butterfly minor of a cylindrical grid, then D has a planar embedding such that D * admits a dijoin path (Theorem 5). Observe that D might still have sources and sinks, so the remainder of the proof consists in adding arcs to D in order kill all sources and sinks (Lemma 2).

Theorems 4 and 5 have the following important corollary:

Corollary 1. Any digraph D without sources or sinks is a butterfly minor of a cylindrical grid iff D admits a planar embedding s.t. D * has a dijoin path.

Note that the planar digraph R in Figure 2 is acyclic. So, whatever be its planar embedding, the dual is strongly connected, i.e., R * has no dicuts. Therefore, every planar embedding of R is such that R * has a trivial dijoin path (the empty path). Therefore, unfortunately, there is no hope that the condition on sources and sinks can be removed from Corollary 1.

Note that any strongly connected digraph (or strong) D satisfies the conditions of Corollary 1. Together with the result of Amiri et al. [START_REF] Amiri | The Erdos-Pósa property for directed graphs[END_REF], this implies that: Corollary 2. Any strong digraph D has the EP property for butterfly minors if, and only if, D admits a planar embedding such that D * has a dijoin path. By Whitney's Theorem [START_REF] Whitney | 2-isomorphic graphs[END_REF], any weakly 3-connected planar digraph D has a unique (up to the outerface) planar embedding (computable in linear time). Since deciding whether the dual of a plane digraph admits a dijoin path can be done in linear time, then our result has the following algorithmic application: Corollary 3. Deciding whether a weakly 3-connected strong digraph has the EP property for butterfly minors can be done in linear time.

Section 2 is devoted to defining the main notions and to present previously known results used in this paper. Section 3 is devoted to digraphs with neither sources nor sinks. Section 4 is devoted to obtaining the supergraph with neither sinks nor sources.

Preliminaries

Planar digraphs and duality. In this section, we present a number of simple known facts concerning planar graphs and their duals. The interested reader can find formal definitions and proofs for such facts in most books on graph theory (e.g., [START_REF] West | Introduction to Graph Theory[END_REF]).

Given a digraph D = (V, A) and e ∈ A, let D \ e = (V, A \ {e}) and let D/e be the digraph obtained from D after contracting the arc e. A dicut of a digraph D = (V, A) is a partition (X, V \ X) of the vertex-set such that X is a non empty proper subset of V and there are no arcs from V \ X to X. The arc-set of (X, V \ X) is the set of arcs from X to (X, V \ X). A dijoin X ⊆ A(D) of D is a set of arcs intersecting all dicuts' arc-sets of D. A dijoin path (resp., dijoin walk ) of D is a dijoin inducing a directed path (resp., directed walk) in D. That is, a dijoin path/walk P of D is a directed path/walk whose arc-set intersects the arc-set of every dicut of D.

Observation 2 A digraph D admits a dijoin path if, and only if, the decomposition of D into strongly connected components has a single source component and a single sink component.

Observation 3 Let D = (V, A) be a digraph with a dijoin path P , and e ∈ A \ A(P ). Then, P is a dijoin path of D \ e.

Observation 4 Let D = (V, A) be a digraph with a dijoin path P , and e ∈ A. Let P ′ be obtained from P by contracting e if e ∈ A(P ), and P ′ = P otherwise. Then, P ′ is a dijoin walk of D/e. Observation 5 Let D = (V, A) be a digraph with a dijoin path P , and v ∈ V be an isolated vertex. Then, P is a dijoin path of D \ v.

Observation 6 Every digraph with a dijoin walk admits a dijoin path.

Butterfly models and cylindrical grids. We now present the formal definition of butterfly models. Let G and H be two digraphs. A (butterfly) model of G in H is a function η : V (G) ∪ A(G) → S(H), where S(H) denotes the set of all subdigraphs of H, such that:

-for every v ∈ V (G), η(v) is a subdigraph of H being the orientation of some tree such that V (η(v)) can be partitioned into ({r v }, I v , O v ) where • η(v)[O v ∪ {r v }
] is an out-arborescence rooted in r v (thus in which all non-root vertices have in-degree 1), called the out-tree of v,

• η(v)[I v ∪ {r v }]
is an in-arborescence rooted in r v (thus in which all nonroot vertices have out-degree 1), called the in-tree of v; for every two distinct u, v ∈ V (G), η(u) and η(v) are vertex-disjoint; for every (x, y) ∈ A(G), η(xy) is a directed path of H from the out-tree of x to the in-tree of y, with internal vertices disjoint from every vertex of η(u) for every u ∈ V (G), and from every internal vertex of η(uv) for every (u, v) ∈ A(G) \ {(x, y)}.

Throughout this work, given a model of G in H, we will refer to the arcs e ∈ A(H) ∩ f ∈A(G) A(η(f )) as the blue arcs of the model, and to the arcs e ∈ A(H) ∩ v∈V (G) A(η(v)) as the black arcs. A vertex of H incident to at least one black arc will be referred to as a black vertex. Fig. 3: A planar embedding of the cylindrical grid C 6,6 . The red directed path Q * 6,6 is the dijoin path defined and used in Section 4.

A model of G in H is minimal if, for every v ∈ V (G) and for every leaf w of η(v), w is incident to some blue arc. Note that, up to removing the leaves that do not satisfy this property from η(v), we can always assume to be working on a minimal model.

Butterfly contracting an arc (u, v)

∈ A(D) of some digraph D consists in contracting the arc (u, v) if d -(v) = 1 or d + (u) = 1. A digraph G is a butterfly minor of some digraph H if G can
be obtained from H by deleting arcs, deleting vertices, and butterfly contracting arcs. Note that if G is a butterfly minor of H, then G can be obtained by first removing some arcs, then removing isolated vertices, and finally performing butterfly contractions.

Observation 7 [START_REF] Amiri | The Erdos-Pósa property for directed graphs[END_REF] A digraph G is a butterfly minor of some digraph H if, and only if, G has a butterfly model in H.

We now deal with cylindrical grids. Let n, m ∈ N * . The cyclindrical grid C n,2m can be seen as a set of n concentric directed cycles having the same direction and linked through 2m directed paths that alternate directions (see Figure 3). Formally, C n,2m is the digraph with vertex-set {(i, j) | 0 ≤ i < n, 0 ≤ j < 2m}, and with the following arc-set. For every 0 ≤ i < n and 0 ≤ j < 2m, we have ((i, j), (i, j + 1 mod m)) ∈ A(C n,2m ), and the directed cycle induced by {(i, j) | 0 ≤ j < m} is called the i th column of C n,2m . For every 0 ≤ i < n -1 and 0 ≤ j < m, we have ((i, 2j), (i + 1, 2j)) ∈ A(C n,2m ) and ((i, 2j + 1), (i -1, 2j + 1)) ∈ A(C n,2m ). Moreover, for every 0 ≤ j < 2m, the directed path induced by {(i, j) | 0 ≤ i < n} is called the j th row of C n,2m .

Throughout this work, we consider that any C n,2m is embedded in the plane so that its first column coincides with the outerface (see Figure 3). Hence, we may naturally refer to left/right and top/bottom such that the first (last) column is the leftmost (rightmost) and the first (last) row is the bottommost (topmost). The arcs of a column are referred to as vertical arcs. Note that all vertical arcs are going up. The arcs of a row are the horizontal arcs. Moreover, the arcs of even (resp., odd) rows are horizontal to the right (resp., to the left). Since C n,2m is strong, we get that C * n,2m is a DAG. Moreover, C * n,2m has a unique sink t * , corresponding to the outerface of the given embedding of C n,2m , and a unique source s * , corresponding to the face of C n,2m bounded by the last column of C n,2m . Note that if P * is any directed path from s * to t * in C * n,2m , then P * is a dijoin path, i.e., it intersects all dicuts of C * n,2m (or, equivalently, P * "crosses" all directed cycles of C n,2m ).

Let η be a butterfly model of a digraph G in C n,2m . We will deal with η through a few operations. Due to lack of space, we only present them informally.

-Adding one column between columns i and i + 1 in η consists in considering the new model η ′ of G in the cylindrical grid C n+1,2m obtained as follows.

Roughly, the left part of the model (between columns 0 to i) does not change, one new column is added (with abscissa i+1), and the right part of the model (between former columns i+1 to n) is translated by one column to the right. The horizontal arcs of the model that were going from former columns i to i + 1 are subdivided once, i.e., they are now directed paths that go from column i to column i + 2. Note that no vertical arcs of the added column belong to the new model η ′ of D. See Figure 4 for an illustration. -Adding two rows between rows j and j + 1 in η consists in considering the new model η ′ of G in the cylindrical grid C n,2(m+1) defined as follows. All the elements of the model below row j, or in row j, remain the same, all elements of the model above row j are translated up from two rows, and all vertical arcs from former row j to former row j + 1 are subdivided twice, i.e., they are now vertical directed paths with three arcs from row j to row j + 3. Note that no horizontal arcs of the two added rows belong to the new model η ′ of D. See Figure 4 for an illustration.

Digraphs with neither sources nor sinks

Let D be a plane digraph such that D * has a dijoin path P * with arcs (e * 1 , • • • , e * p ). Let D P * (s, t) be obtained from D as follows (see Figure 5 to follow the construction). For every i ∈ {1, • • • , p}, let e i = (u i , w i ) be the arc of D corresponding to e * i . Subdivide e i into three arcs (u i , t i ), (t i , s i ), and (s i , w i ). Then, remove (t i , s i ), and, for every i ∈ {1, • • • , p}, identify the vertices t 1 , • • • , t p into one vertex t, and the vertices s 1 , • • • , s p into one vertex s. Finally, add an arc from s to t. Note that V (D P * (s, t)) = V (D) ∪ {s, t} and, for every v ∈ V (D), the in-degree (resp., out-degree) of v in D is the same as in D P * (s, t). Since P * is a dijoin path of D * , the set {e i } i≤m is a feedback arc set of D [START_REF] Bang-Jensen | Digraphs Theory, Algorithms and Applications[END_REF]. Therefore:

Observation 8 Let D be a plane digraph such that D * has a dijoin path P * . If D has neither sources nor sinks, then D P * (s, t) is a planar DAG having s as unique source and t as unique sink.

A visibility representation of a graph G is a mapping of V (G) into nonintersecting horizontal segments3 {h u } u∈V (G) , together with a mapping {t e } e∈E(G) of the edges into vertical segments such that for every uv ∈ E(G), we get that t uv has endpoints in h u and h v , and t uv does not cross h w for every w ̸ = u, v.

Theorem 2 ([3]). Every planar graph admits a visibility representation.

Here, we apply the approach presented in [START_REF] Tamassia | A unified approach to visibility representations of planar graphs[END_REF] to our context in order to obtain a butterfly model of a planar digraph D into a cylindrical grid, if one exists. For this, we slightly adapt their definitions to our purposes.

We consider a visibility representation ({h u } u∈V , {t e } e∈A ) of D = (V, A) to be drawn on the plane, and, given two horizontal (vertical) segments s 1 , s 2 , we write s 1 ≤ s 2 if the y-coordinate (x-coordinate) of s 1 is smaller than the one of s 2 . Now, given a DAG D = (V, A), we say that a visibility representation ({h u } u∈V , {t e } e∈A ) of D is increasing if h u ≤ h v for every arc (u, v) ∈ A (in other words, the arcs are all directed upwards).

In [START_REF] Tamassia | A unified approach to visibility representations of planar graphs[END_REF], in order to construct a visibility representation, the authors show that they can obtain an orientation D of a graph G that is acyclic, has exactly one source s and exactly one sink t, and (s, t) ∈ A(D) (they call such a digraph a PERT-digraph). After they obtain this orientation, they use a total order (v 1 , . . . , v n ) of V (G) that meets the orientation D, and then construct a visibility representation such that s 1 < s 2 < . . . < s n , where s i denotes the ycoordinate of h vi , for every i ∈ {1, . . . , n}. Observe that, because the order meets the orientation, we get that this is an increasing visibility representation. Their representation also has the property that the x-coordinate of arc (s, t) is smaller than the x-coordinate of every other edge of G. In short, even though they use a different terminology, the results presented in [START_REF] Tamassia | A unified approach to visibility representations of planar graphs[END_REF] actually show that the theorem below holds. The interested reader can check this is true by observing, in their algorithm W-VISIBILITY, that after they obtain the desired orientation D (line 2), they only work on D itself; also, the increasing order over the y-coordinates is ensured in line 5.1 of their algorithm.

Theorem 3 ([9]

). Let D be a planar DAG with unique source s and unique sink t, and such that (s, t) ∈ A(D). Then, D admits an increasing visibility representation such that each horizontal segment has a distinct y-coordinate, and the x-coordinate of the segment of (s, t) is smaller than the x-coordinate of the segment of every other arc of D. Sketch of the proof. By Observation 8, D P * (s, t) is a DAG with a unique source s, a unique sink t, and (s, t) ∈ A(D P * (s, t)). By Theorem 3, there exists an increasing visibility representation of D P * (s, t). Let V (D P * (s, t)) = {s = v 1 , . . . , t = v n } be ordered increasingly according to their y-coordinates on the representation and suppose, without loss of generality, that the y-coordinate of h v1 = h s is 0 and the difference between the y-coordinates of h vi and h vi-1 is 2 (their value on the constructed increasing visibility representation are all different, so we just need to adjust it). Observe that, in this case, the y-coordinate of h vi is 2i -2. We will build a model of D in some cylindrical grid as follows.

For each v i ∈ V (D) (hence i / ∈ {1, n}), let h ′ vi be the segment equivalent to h vi , but in the upper row. In other words, h ′ vi has y-coordinate 2i -1, and leftmost and rightmost x-coordinates equal to the ones of h vi . The idea of the proof is to relate v i with the path formed by the union of paths associated to h ′ vi and h vi in the cylindrical grid. Since all arcs of D point upwards, we get that the subpath associated to h ′ vi (i.e., in row 2i -1) corresponds to the out-tree of v i , while the subpath associated to h vi (i.e., in row 2i -2) corresponds to the in-tree of v i . ◁

Note that Theorem 4 allows us to prove the "if" part of Theorem 1.

Theorem 5. If a digraph D = (V, A) has a butterfly model in C n,2m for some n, m ∈ N * , then D has a planar embedding such that D * admits a dijoin path.

Proof. Consider the planar embedding of C n,2m such that the outerface contains its first column (see Figure 3) and let P * be any directed path from the single source of C * n,2m to its single sink. Note that P * is a dijoin path of C * n,2m . By Observation 7, D is a butterfly minor of C n,2m . Let s 1 , • • • , s q be the sequence of operations allowing to get D from C n,2m where these operations are ordered in such a way that first arcs are removed, then isolated vertices are removed and, finally, butterfly contractions are performed. For every 0 ≤ i ≤ q, let G i be the digraph obtained after the i th operation (so G 0 = C n,2m and G q = D). We show, by induction on 0 ≤ i ≤ q, how to obtain a directed path P i which is a dijoin path of G * i . In particular, it holds for i = 0 by taking

P 0 = P * . Let i ≥ 1. If s i consists in removing an arc e i of G i-1 then, if e * i ∈ A(P i-1 ), let P ′ i = P i-1 /e * i ,
i = (u, v) ∈ A(G i-1 ) such that e * i ∈ A(P i-1 ). Let us assume that d -(v) = 1 (the case when d + (u) = 1 is symmetric). Observe that d + (v) > 0 as otherwise e *
i would be a loop, contradicting that P i-1 is a directed path. Then, let {f 1 , • • • , f q } be the set of out-arcs of v ordered clockwise in the embedding of D in the plane. Then, let P ′ i be the directed walk obtained by replacing e * i in P i-1 by the directed walk consisting of the arcs

f * 1 , f * 2 , • • • , f * q . Note that P ′ i is a dijoin walk in G * i . Indeed, consider the set of arcs K of a dicut of G * i . If K is also a dicut in G * i-1
, then e * i / ∈ K and P ′ i intersects K since P i-1 is a dijoin path and so intersects K. Otherwise, e * i ∈ K which implies that {f * 1 , f * 2 , • • • , f * q } ∩ K ̸ = ∅, and so P ′ i intersects K. Finally, by Observation 6, G * i admits a dijoin path P i . ⊓ ⊔ Theorems 4 and 5 prove the following corollary which corresponds to Theorem 1 in the case of digraphs with neither sources nor sinks (and in particular, Corollary 3 is a special case of the following corollary). Corollary 4. A digraph D without sources or sinks is a butterfly minor of a cylindrical grid if, and only if, D admits a planar embedding such that D * has a dijoin path. Moreover, if D is weakly 3-connected, then this can be decided in linear time.

Proof. Due to the weakly 3-connectivity of D, and by Whitney's Theorem, D has a unique (up to the outerface) planar embedding (and a unique dual). Given such an embedding, checking the existence of a dijoin path can be done in linear time by Observation 2.

⊓ ⊔

Recall that a strong digraph D has the EP property for butterfly minors iff D is a butterfly minor of a cylindrical grid [START_REF] Amiri | The Erdos-Pósa property for directed graphs[END_REF]. Together with our result, we get: Corollary 3. Deciding whether a weakly 3-connected strong digraph D has the EP property for butterfly minors can be done in linear time.

Digraphs with sources and sinks

We have seen that if D is a butterfly minor of a cylindrical grid, then D has a planar embedding such that D * admits a dijoin path (Theorem 5). As we want to show that this holds for a spanning supergraph with neither sources nor sinks, it remains to "kill" sources and sinks in D. This is done in this section.

Given a cylindrical grid C n,2m with the canonical planar embedding described previously, let Q * n,2m be the directed path of the dual C * n,2m whose arcs correspond exactly to all arcs of C n,2m that go from the last (topmost) row to the first (bottommost) row. Note that Q * n,2m is a dijoin path of C * n,2m (see Figure 3). In what follows, given a source s in D (resp., a sink t), we describe a process that builds a model for an in-arc that we add to s (resp., an out-arc that we add to t), so that the obtained supergraph has also a model in a cylindrical grid and has one less source (resp., sink). By iteratively applying such process, we get the desired conclusions.

Let us consider a butterfly model η of D with a dijoin path P * as in Lemma 1, and suppose that D has a source s (the case of a sink is symmetric). We will add a new arc (z, s) for some z ∈ V (D), and a directed path Q (finishing in the in-tree of the model of s) for modelling this arc in the existing model η. The difficulty is to find the vertex of an out-tree in which we can start Q from. First let us add two columns between any two consecutive columns and let us add two rows between any two consecutive rows. We also add one column to the left and one column to the right of the cylindrical grid.

Let r s be the root of η(s). Note that, by assuming η to be minimal, we get that the in-tree of the model of s in η is reduced to its root. Let a 1 be the vertex below r s and b 1 the vertex below a 1 . Since we have just added two rows between any two rows, and because the in-tree of s is reduced to r s , we get that a 1 , b 1 are not part of the model of any vertex nor arc. Let Q initially contain just the arc (a 1 , r s ) (this will actually be the last arc of Q). Let us assume that Q has been built up to some vertex a h , i.e., Q = (a h , a h-1 , • • • , a 1 , r s ), and additionally assume that the vertex b h below a h is not part of the model of any vertex nor arc (this is the case for h = 1). Let w be the vertex below b h .

-If w is not part of the model of any vertex nor arc, then let a h+1 = b h and let b h+1 = w, and we continue to build Q. -If w is in the out-tree of some vertex, then add (w, b h ), (b h , a h ) to the end of Q to be done. -If w is part of the in-tree of some vertex a (and not of its out-tree, i.e., w is not the root of the model of a), then assume that the row of a h goes to the right (the other case is symmetric). Let x be the left neighbor of a h , y be the vertex below x (and to the left of b h ), and z the vertex below y (and to the left of w). Note that, since w is part of the model and b h is not, then the rows of b h and a h are rows that have been added just before starting the process.

In particular, this implies that either both x and y belong to the model of some e ∈ V (D) ∪ A(D), or neither x nor y is part of any model. We can then prove that the former case is not possible because it would contradict the fact that w is part of the in-tree (and not of the out-tree) of the model of a.

In the latter case, we set a h+1 = x and b h+1 = y and go on. -If w is part of the model of some arc e = (u, v) ∈ A(D). We apply similar arguments and omit the proof because of space constraints.

The above process is not ensured to finish because if might happen that vertices a h and b h are already on the outerface of the model η. The next two cases allow to ensure that our process will actually terminate. For this purpose, we use the dijoin path P * .

-If (b h , a h ) crosses the dijoin path P * and P * does not cross any blue arc, then let us consider the closest row under P * that contains a vertex of the model. W.l.o.g., let us assume that this row goes to the right and let x be the rightmost vertex of this row that is part of the model of some vertex v * of D. By minimality of the model and because x has no out-neigbour in the model of any vertex or arc, then, x must be the root of η(v * ) (which is actually an in-tree). Now, we add to η(v * ): the up-going arc (x, y) (y being the up-neighbor of x), and the horizontal directed path Y starting from y to the leftmost vertex of this row (then y becomes the new root of η(v * ) and the path Y will be considered as its out-tree). To conclude this case, add at the beginning of Q, the directed path from the path Y of η(v * ) (added in previous paragraph) to b h . -If (b h , a h ) crosses P * which crosses some blue arc, then we apply similar arguments and omit the proof because of space constraints.

◁

Further work. An interesting question is whether there exists a structural condition on the sources and sinks of a digraph D that corresponds to being a butterfly minor of a cylindrical grid (avoiding to invoke a supergraph without sources or sinks). This may help to answer the question of the computational complexity of deciding if a strong digraph D has the EP property when D is not weakly 3-connected. Since the class of digraphs that are butterfly minors of a cylindrical grid is closed under taking butterfly minors, it would also be interesting to characterize the minimal forbidden butterfly minors for this class.

A Basic results

In this section, we present a number of simple known facts concerning planar graphs and their duals. The interested reader can find proofs for such facts in most graph theory books. We refer to [START_REF] West | Introduction to Graph Theory[END_REF].

In a digraph, a vertex with no in-neighbors (resp., no out-neighbors) is called a source (resp. a sink). A plane (di)graph D is a planar (di)graph together with a planar embedding. Given a plane undirected graph G = (V, E), let G * = (V * , E * ) be its dual. That is, the dual graph G * of G (with a fixed planar embedding) is the graph that has a vertex in V * for each face of the embedding of G and G * has an edge e * = {u, v} ∈ E * for each two faces u and v in the embedding of G that are separated from each other by an edge e ∈ E. The edge e * is the dual edge of e. If a same face appears on both sides of an edge e ∈ E, then e * is a self-loop of G * . For a plane digraph D, the dual graph D * is made directed as well, by orienting each dual arc e * by a 90°clockwise turn from the corresponding primal arc e. For instance, if a face of a plane digraph D is "surrounded" by a directed cycle oriented clockwise (resp., counter-clockwise), then the corresponding vertex of D * is a source (resp., a sink). Note that D * is also a plane digraph and that (D * ) * is nothing but the digraph obtained from D by reversing all arcs. A digraph D = (V, A) is strong if and only if, for every distinct u, v ∈ V , there exists a directed u, v-path in D. D is a Directed Acyclic Graph (DAG) if it is acyclic, i.e., it has no directed cycle.

Recall the folklore fact that, in the context of planar digraphs, being acyclic and being strong are dual notions. Recall the definitions of dijoin and feedback arc set. The following observation is well known.

Observation 10 ([2]) Let D = (V, A) be a plane digraph. A set of arcs X ⊆ A(D) is a dijoin of D if, and only if, {e * ∈ A(D * ) | e ∈ X} is a feedback arc set of D * .
Given a digraph D, its decomposition into strongly connected components is the digraph D ′ having a vertex v C for each C of the (maximal) strongly connected components of D, and in which two vertices v C and v C ′ are joined by an arc from v C to v C ′ if there is an arc from C to C ′ in D. Note that D ′ is always a DAG. A source (resp., a sink) of D ′ is called a source component (resp., a sink component). These notions relate to dijoin paths in the following way.

Observation 2 A digraph D admits a dijoin path if, and only if, the decomposition of D into strongly connected components has a single source component and a single sink component.

Proof of the claim. Assume that the decomposition of D into strongly connected components has a single source component S and a single sink component T . Let P be any directed path of D from any vertex of S to any vertex of T . Let (X, V \ X) be any dicut with arc-set C ⊆ A. Then, S ⊂ X and T ⊂ V \ X. Therefore, A(P ) must intersect C, and so P is a dijoin path.

On the other hand, assume that the decomposition of D into strongly connected components has at least two source components S and S ′ (the case when it has at least two sink components being symmetric). Let P be any directed path in D. W.l.o.g., P has no vertex in S ′ . Then C = (S ′ , V \ S ′ ) is a dicut and P does not intersect its arc-set. Hence, P is not a dijoin path of D. ⋄

We finish off with a few facts on dijoin paths.

Observation 3 Let D = (V, A) be a digraph with a dijoin path P , and e ∈ A \ A(P ). Then, P is a dijoin path of D \ e.

Note that if the arc e that is contracted in the observation below has its two ends in P (but e is not in P ) then it may imply that P ′ is not a path anymore (but a walk). This issue is dealt with in the following Observation 6.

Observation 4 Let D = (V, A) be a digraph with a dijoin path P , and e ∈ A. Let P ′ be obtained from P by contracting e if e ∈ A(P ), and P ′ = P otherwise. Then, P ′ is a dijoin walk of D/e. Observation 5 Let D = (V, A) be a digraph with a dijoin path P , and v ∈ V be an isolated vertex. Then, P is a dijoin path of D \ v.

Observation 6 Every digraph with a dijoin walk admits a dijoin path.

Proof of the claim. Let P = (v 1 , • • • , v p ) be a shortest dijoin walk of D and, for purpose of contradiction, let us assume that P is not a dijoin path. That is, there are i < j such that

v i = v j . Since (v i , • • • , v j ) is a directed cycle, for every dicut (X, V \ X), either {v i , • • • , v j } ⊆ X or {v i , • • • , v j } ⊆ V \ X. Hence, the arc-set of P ′ = (v 1 , • • • , v i , v j+1 , • • • , v p )
also intersects the arc-sets of all dicuts. Therefore, P ′ is a shorter dijoin walk, a contradiction. ⋄

Recall that a model of G in H is minimal if, for every v ∈ V (G) and for every leaf w of η(v), w is incident to some blue arc. Up to removing the leaves that do not satisfy this property from η(v), we get that the following holds:

B Formal definition of the adding rows or columns operations

We will deal with butterfly models of a digraph in C n,2m through a few operations. Let η be a butterfly model of a digraph D in C n,2m . Due to lack of space, we only present them informally.

-Adding x ≥ 1 columns between columns i and i+1 in η consists in considering the new model η ′ of G in the cylindrical grid C n+x,2m defined as follows.

Intuitively, all the elements of the model to the left of column i (or in column i) remain the same, all elements of the model to the right of column i are translated from x columns toward the right and all horizontal arcs from column i to column i + 1 are replaced by horizontal paths with x + 1 arcs (from the column i to the column i + x + 1 in the resulting model). More formally, for every y ∈ V (G) ∪ A(G) and for every e = ((ℓ, j), (ℓ ′ , j ′ )) ∈ η(y), if ℓ, ℓ ′ ≤ i, then e ∈ η ′ (y), if ℓ, ℓ ′ > i, then ((ℓ+x, j), (ℓ ′ +x, j ′ )) ∈ η ′ (y). Finally, if ℓ = i and ℓ ′ = i+1 (so j = j ′ ), then the arcs ((ℓ, j), (ℓ+1, j)), ((ℓ+ 1, j), (ℓ+2, j)), • • • , ((ℓ+x, j), (ℓ+x+1, j)) are added to η ′ (y). Symmetrically, if ℓ = i + 1 and ℓ ′ = i (so j = j ′ ), then the arcs ((ℓ + 2x + 1, j), (ℓ + 2x, j)), ((2x, j), (2x -1, j)), • • • , ((ℓ + 1, j), (ℓ, j)) are added to η ′ (y). Note that no vertical arcs of the x added columns belong to the new model η ′ of D. See Figure 4 for an illustration. -Adding 2x ≥ 2 rows between rows j and j + 1 in η consists in considering the new model η ′ of G in the cylindrical grid C n,2(m+x) defined as follows. For every y ∈ V (G) ∪ A(G) and for every e = ((i, ℓ), (i ′ , ℓ ′ )) ∈ η(y), if ℓ, ℓ ′ ≤ j, then e ∈ η ′ (y), if ℓ, ℓ ′ > j, then ((i, ℓ + 2x), (i ′ , ℓ ′ + 2x)) ∈ η ′ (y). Finally, if ℓ = j and ℓ ′ = j + 1 (so i = i ′ ), then the arcs ((i, ℓ), (i, ℓ + 1)), ((i, ℓ + 1), (i, ℓ + 2)), • • • , ((i, ℓ + 2x), (i, ℓ + 2x + 1)) are added to η ′ (y). Note that no horizontal arcs of the 2x added rows belong to the new model η ′ of D. See Figure 4 for an illustration.

C Omitted proofs from Section 3 Proof. By Observation 8, D P * (s, t) is a DAG with a unique source s, a unique sink t, and (s, t) ∈ A(D P * (s, t)). By Theorem 3, there exists an increasing visibility representation of D P * (s, t). Let V (D P * (s, t)) = {s = v 1 , . . . , t = v n } be ordered increasingly according to their y-coordinates on the representation and suppose, without loss of generality, that the y-coordinate of h v1 h s is 0 and the difference between the y-coordinates of h vi and h vi-1 is 2 (their value on the constructed increasing visibility representation are all different, so we just need to adjust it). Observe that, in this case, the y-coordinate of h vi is 2i -2. We will build a model of D in some cylindrical grid as follows.

For each v i ∈ V (D) (hence i / ∈ {1, n}), let h ′ vi be the segment equivalent to h vi , but in the upper row. In other words, h ′ vi has y-coordinate 2i-1, and leftmost and rightmost x-coordinates equal to the ones of h vi . The idea of the proof is to relate v i with the path formed by the union of paths associated to h ′ vi and h vi in the cylindrical grid (see Figure 6). Since all arcs of D are "pointing upwards", we get that the subpath associated to h ′ vi (i.e., in row 2i -1) corresponds to the out-tree of v i , while the subpath associated to h vi (i.e., in row 2i-2) corresponds to the in-tree of v i . We formalize this proof in what follows.

Because D P * (s, t) is finite, we can suppose that the coordinates of the endpoints of the segments ({h u } u∈V (D P * (s,t)) , {t e } e∈A(D P * (s,t)) ) are all integers. Let k ∈ N be equal to the maximum x-coordinate of some arc. We first construct a butterfly model η of D P * (s, t) into the cylindrical grid C k,2n as follows.

For every 1 ≤ i ≤ n, let (j, 2i -2) and (ℓ, 2i -2) be the coordinates of the leftmost and rightmost points of h vi respectively (j ≤ ℓ). Let P i be the subpath of the cylindrical grid whose first vertex is (j, 2i -2) and last vertex is (ℓ, 2i -2). Note that 2i-2 being even, the corresponding row goes to the right. Let Q i be the path whose first vertex is (ℓ, 2i-1) and last vertex is (j, 2i-1) (the corresponding row goes to the left). Let us define η(s

) = η(v 1 ) = Q 1 , η(t) = η(v n ) = Q n and, for every 1 < i < n, let η(v i ) = P i ∪ ((ℓ, 2i -2), (ℓ, 2i -1)) ∪ Q i . For 1 < i < n, we can consider η(v i )
as an in-out-branching with root (ℓ, 2i -2). Observe that, for every v i ̸ = v j , since h vi and h vj have different y-coordinates, and the difference between the y-coordinates of h vi and h vi-1 is 2, η(v i ) and η(v j ) are vertexdisjoint.

For the vertical segments {t e } e∈A(D P * (s,t)) , that represent the arcs of D P * (s, t), if t vivj is a segment with endpoints in h vi and h vj with x-coordinate m, for i < j, we make η(v i v j ) = ((m, 2i -1), (m, 2i), (m, 2i + 1), . . . , (m, 2j -2)), where (m, 2i -1) ∈ Q i and (m, 2j -2) ∈ P j . So, η(v i v j ) is a path from the out-branching of η(v i ) to the in-branching of η(v j ). Since the vertical segments are non-overlapping and by the way we model the vertices of D P * (s, t) through the visibility representation, η(e) and η(e ′ ) are vertex-disjoint, for every distinct e, e ′ ∈ A(D P * (s, t)). Now, we want to use η to construct a butterfly model ν of D in some cylindrical grid C k,2l (initially, l = n but it might increase during the process below). Start by letting ν(u) = η(u), for every u ∈ V (D) (i.e., we ignore vertices s and t), and let N + D P * (s,t) (s) \ {t} = {w 1 , . . . , w p }, and N - D P * (s,t) (t) \ {s} = {u 1 , . . . , u p }. Observe that, for each m ∈ {1, . . . , p}, there is a path η(u m , t) = ((j m , i), (j m , i+ 1), . . . (j m , 2n -2)) that models arc (u m , t) (note that i = 2j -1 where j is the index such that u m = v j ). The value j m is called the x-coordinate of u m . Similarly, there is a path η(s, w m ) = ((ℓ m , 1), (ℓ m , 2), . . . (ℓ m , i ′ )) that models arc (s, w m ) (where i ′ = 2j ′ -2 where j ′ is the index such that w m = v j ′ ), and let ℓ m be the x-coordinate of w m , for each m ∈ {1, • • • , p}.

Note that, the arcs in {(u i , w i ) | 1 ≤ i ≤ p} are exactly the arcs of D that are not modeled in η. Recall that these arcs are ordered according to the path P * (see Figure 5). We start with ν(u i , w i ) = η(u i , t) ∪ η(s, w i ). Note that (j i , 2n -2) (resp., (ℓ i , 1)) are the coordinates of the topmost (resp., bottommost) endpoint of η(u i t) (resp., of η(sw i )). Let us add 2n rows between the row 2n -2 and the row 1. Since j 1 ≤ • • • , j p and ℓ 1 ≤ • • • , ℓ p , there are p vertex-disjoint directed paths (H i ) 1≤i≤p from (j i , 2n -2) to (ℓ i , 1) respectively, using the 2n new rows.

For every 1 ≤ i ≤ p, add H i to ν(u i , w i ). ⊓ ⊔

D Omitted proofs from Section 4

Observation 12 Let D = (V, A) be a digraph. If D has a butterfly model in C n,2m , then D has a butterfly model in C n ′ ,2m ′ for some n ′ ≥ n and m ′ ≥ m such that every blue arc with tail a black vertex is vertical.

Proof. Consider any blue arc (u, v) ∈ A(C n,2m ) of the model η of D such that its tail is black. Note that it means that u is a vertex of the out-tree of η(w * ) for some w * ∈ V (D) and that there exists an arc

a * = (w * , x) ∈ A(D) such that (u, v) ∈ A(η(a * )). Let (i, j) be the coordinates of u in C n,2m .
Let us assume that (u, v) is horizontal to the right (i.e., v has coordinates (i + 1, j)). The case when (u, v) is horizontal to the left is symmetric. Let us describe a transformation (which is depicted in Figure 7) that will give a new model ν where this blue arc has been "turned up" (i.e., it becomes a vertical arc).

First add one column between columns i and i + 1. The new column is then index i + 1. Intuitively, we move up the part to the left of the new column i + 1 (included) from row j + 1, then we move up the part to the right of column i + 1 from row j. In other words, we subdivide twice all edges between row j and j + 1

j u v i (a) Original model j + 2 j i i + 1 (b) Turning up the arc (u, v)
Fig. 7: Illustration of operation performed on arc (u, v) in the proof of Observation 12. Rows and column highlighted in green are the "added" rows and column. The red lines emphasize the last modifications.

that are to the left of column i + 1, and all edges between row j -1 and j that are to the right of column i + 1. The only possible interaction between left and right (and up and down) that is not naturally within an embedding in a bigger cylindrical grid is the one between columns i and i+1 in row j. This is considered in a last step by increasing the out-tree of w * with the arc ((i, j), (i+1, j)), while removing the same arc from η(a * ) and adding arcs ((i + 1, j), (i + 1, j + 1)) and ((i + 1, j + 1), (i + 1, j + 2)) to η(a * ). The formal arguments are presented below. Now, let us formally define the above transformation. First, a new column is added between columns i and i + 1, according to the transformation defined in the preliminaries section. The new column has now abscissa i + 1 and recall that no vertical arc of this column belongs to the model of any vertex or arc of D.

Let B be the set of vertices (x, y) of the grid such that either y < j, or y = j and x < i + 1, and let T be the remaining vertices (i.e., (B, T ) is a partition of the vertices of the cylindrical grid). Note that the only arcs of the model of D that go from one part to the other are: the arc ((i, j), (i+1, j)) (that results from the subdivision of (u, v) when the new column has been added); the vertical arcs of the form ((ℓ, j)(ℓ, j + 1)) with ℓ ≤ i or ((ℓ, j -1)(ℓ, j)) with ℓ > i; and the vertical arcs between the topmost row and the bottommost row, i.e., of the form ((ℓ, 2m -1), (ℓ, 0)). The new model η ′ is defined as follows:

for every arc (a, b) of the model of e ∈ V (D) ∪ A(D), i.e., (a, b) ∈ A(η(e)), such that a and b belong to B, then (a, b) ∈ A(η ′ (e)); for every arc ((ℓ, h), (ℓ ′ , h ′ )) of the model of e ∈ V (D)∪A(D), i.e., ((ℓ, h), (ℓ ′ , h ′ )) ∈ A(η(e)), such that (ℓ, h) and (ℓ ′ , h ′ ) belong to T , then ((ℓ, h+2), (ℓ ′ , h ′ +2)) ∈ A(η ′ (e)); for every arc ((ℓ, 2m -1), (ℓ, 0)) of the model of e ∈ V (D) ∪ A(D), i.e., ((ℓ, 2m -1), (ℓ, 0)) ∈ A(η(e)), then ((ℓ, 2m + 1), (ℓ, 0)) ∈ A(η ′ (e)); for every arc ((ℓ, j)(ℓ, j + 1)) with ℓ ≤ i such that ((ℓ, j)(ℓ, j + 1)) ∈ A(η(e))

for some e ∈ V (D) ∪ A(D), then ((ℓ, j)(ℓ, j + 1)), ((ℓ, j + 1)(ℓ, j + 2)) and ((ℓ, j + 2)(ℓ, j + 3)) are added to η ′ (e); for every arc ((ℓ, j -1)(ℓ, j)) with ℓ > i such that ((ℓ, j -1)(ℓ, j)) ∈ A(η(e))

for some e ∈ V (D) ∪ A(D), then ((ℓ, j -1)(ℓ, j)), ((ℓ, j)(ℓ, j + 1)) and ((ℓ, j + 1)(ℓ, j + 2)) are added to η ′ (e); -Finally, the arc ((i, j),

(i + 1, j)) is added to η ′ (w * ) (recall that w * ∈ V (D) is
the vertex whose u is part of the out-tree) and the arcs ((i+1, j)(i+1, j +1)) and ((i + 1, j + 1)(i + 1, j + 2)) are added to η(a * ) (recall that (u, v) was part of the model of a * ∈ A(D)).

Let us show that η ′ is a valid model of D. Indeed, consider any path P in η. If all vertices of P belong to B, then P is invariant by the transformation. If all vertices of P belong to T , then the image of P in η ′ is the same path moved up by two rows (in particular, the orientations of the horizontal arcs remain consistent). Or P = P ′ ⊙ a ⊙ Q ′ (where ⊙ denotes the concatenation) with P ′ is a path with all its vertices in B, Q ′ is a path with all vertices in T and the arc a is (1) either (u, v), or (2) an arc ((ℓ, j)(ℓ, j + 1)) with ℓ ≤ i or (3) an arc ((ℓ, j -1)(ℓ, j)) with ℓ > i. In all cases, P ′ remains invariant and Q ′ is translated up by two rows. In cases (2) and (3), the image of a by η ′ is a path of length 3 that connects the last vertex of the image of P ′ to the first vertex of the image of Q ′ . In the case (1), the image of a is the path with arcs ((i, j), (i + 1, j)), ((i + 1, j)(i + 1, j + 1)) and ((i + 1, j + 1)(i + 1, j + 2)) which again leads to a valid path.

To conclude, the image of a * by η ′ now starts by a vertical blue arc (the arc ((i + 1, j)(i + 1, j + 1))).

Repeating iteratively this process (to all horizontal blue arc with a black vertex as tail) eventually ensures a model that satisfies the statement. Proof. If Q * n,2m does not "cross" any black arc in the given model η, then we are done. Otherwise, let k be the number of black arcs crossed by Q * n,2m and let (x, y) be the leftmost black arc which is the dual of an arc of Q * n,2m . Let v ∈ V (D) such that (x, y) ∈ η(v). Let us assume that (x, y) belongs to the out-tree of η(v) (the case when it is in the in-tree is symmetric). Let T v be the subtree of the out-tree of η(v) induced by (x, y) and all vertices of η(v) that can be reached from y in η(v). Let k ′ be the number of blue arcs with tail in T v . We present a process such that either we strictly decrease k (in the case k ′ = 1), or k remains the same but k ′ decreases. Therefore, eventually (when k = 0), we obtain the desired model. Throughout the proof, we use n ′ , m ′ to denote the dimensions of the current model/path.

-Let us assume that k ′ = 1. Hence, since we may assume that the model is minimal (by Observation 11), then T v is a directed path P . Let e ′ be the blue arc with tail in T v . We have e ′ ∈ η(e) for some arc e = (v, w) ∈ A(D).

Intuitively, we remove P ∪ {(x, y)} from the model of w and add it to the model of e. More formally, let H = η(e) be the directed blue path modeling e. We define the new model η ′ of G in C n ′ ,2m ′ as follows: for every z ∈ E(G) ∪ V (G) \ {v, w, e}, η ′ (z) = η(z). Then, η ′ (v) = η(v) \ (P ∪ {(x, y)}), η ′ (w) = η(w) and η ′ (e) = {(x, y)} ∪ (P ∪ H). Since (x, y) is now a blue arc (and no blue arc has been changed to black), we decreased by one the number of black arcs crossed by Q * n,2m . -Now, let us consider the case when k ′ > 1. We first need some technical modifications of the model.

• First, we would like to ensure that x is on a row going to the right. If x is on a row going to the left, let j be the row of x. We add two rows a and b between rows j and j -1, where a is the row going to the right. We replace Q * n ′ ,2m ′ (which was between rows j and j + 1) by the parallel dijoin path between the new rows j and a. This new path still intersects the same number of black arcs and the only difference is that it intersects T v in the arc (x ′ , y ′ ) (where y ′ = x) and x ′ is a on a row going to the right. Hence, going back to the initial notation, we may assume that x is on a row going to the right.

• Then, we would like that x is not the head of a black or blue vertical arc.

If this is the case, let us apply an operation that ensures that x is not the head of a black or blue vertical arc, and that its left neighbor is also part of the out-tree of v. Let (i, j) be the coordinates of x. First, add one column to the right of x (i.e., between columns i and i+1). Then, remove (x, y) = ((i, j), (i, j + 1)) from η(v) and add ((i + 1, j), (i + 1, j + 1)) to η(v) (this will be our "new" arc crossing Q * n,2m , i.e., replacing (x, y)), add ((i, j), (i + 1, j)) to η(v) (if it was not already part of it) and finally, add ((i + 1, j + 1), (i, j + 1)) to η(v) (note that this last arc was not part of any model because y is in the out-tree of η(v) and had x has unique in-neighbor). Now, the vertices (i + 1, j) and (i + 1, j + 1) play the role of x and y respectively. Hence, we may assume that x is not the head of a black or blue vertical arc and that its left neighbor is also part of the out-tree of v, as we wanted to show. Now, we are ready for the main work. The technical process defined below is depicted in Figure 8. Start a DFS of T v from the arc (x, y) with the following priorities: if possible, go to the left, else if it is possible go up, and go to the right otherwise. Stop as soon as you reach a leaf z of T v . By minimality of the model, z must be the tail of a blue arc e = (z, z ′ ). Note that by Observation 12, we may assume that (z, z ′ ) is a vertical arc. Let P be the subpath of T v from x to z. Let f ∈ A(D) such that e ∈ η(f ). We will increase the cylindrical grid to make "some space". For every column i such that P has at least one vertical arc in column i, add one column between column i -1 and column i. In particular, we add one column to the left of x. For every row j such that P has at least one arc going right in row j, add two rows between rows j and j + 1. Finally, for every row j such that P has at least one arc going left in row j, add two rows between rows j -1 and j. Note that these additions of rows and columns do not change the main properties of the model of D in the new larger grid C n ′ ,2m ′ (abusing the notation we still denote this model by η): blue arcs with head in an intree are vertical, models of vertices are still minimal and, more important, Q * n ′ ,2m ′ still crosses k black arcs and there are k ′ blue arcs with tail in T v . We now modify the model η into a new one η ′ that differs only on v and e. Start with η ′ (q) = η(q) for all q ∈ V (D) ∪ A(D). Now, let x ′ be the left neighbor of x. It exists since we have added a column to the left of (x, y) and x ′ is part of the out-tree of v by the initial technical modifications. Observe also that x ′ is the only in-neighbor of x in T v . Intuitively, we will now add to η ′ (v) a path P ′ that starts in x ′ and is "parallel" to P using the added rows and columns. In what follows, we describe the path P as its sequence of arcs starting from (x, y). In addition to the starting arc, we only need the sequence of orientations: going up (U), right (R) or left (L), of each arc to well describe P . Hence, let P = (α 0 = (x, y), α 1 , • • • , α p ) where α i ∈ {U, R, L} for every 1 ≤ i ≤ p. We build P ′ iteratively starting from the up-going arc (x ′ , y ′ ) where y ′ is the up neighbor of x ′ . Note that, because of the added rows and columns, y ′ cannot be in the model of any element of D. Assume that P ′ = (β 0 = (x ′ , y ′ ), β 1 , • • • , β q ′ ) has already been built and corresponds to the prefix P pref = ((x, y), α 1 , • • • , α q ) of P (it holds for q = q ′ = 0). We extend P ′ depending on the next one, two or three arcs of P .

• If (α q+1 , α q+2 , α q+3 ) = (U U L), add nothing to P ′ . Then, P ′ corresponds to the new prefix P pref = ((x, y), α 1 , • • • , α q+3 ) of P ; • If (α q+1 , α q+2 , α q+3 ) = (RU U ), add nothing to P ′ . Then, P ′ corresponds to the new prefix

P pref = ((x, y), α 1 , • • • , α q+3 ) of P ; • If (α q+1 , α q+2 ) = (U R), add (U U U RR) to P ′ . Then, P ′ corresponds to the new prefix P pref = ((x, y), α 1 , • • • , α q+2 ) of P ; • If (α q+1 , α q+2 ) = (LU ), add (LLU U U ) to P ′ . Then, P ′ corresponds to the new prefix P pref = ((x, y), α 1 , • • • , α q+2
) of P ; • Otherwise, add α q+1 to P ′ . Then, P ′ corresponds to the new prefix P pref = ((x, y), α 1 , • • • , α q+1 ) of P ; Finally, we explain how to deal with η(f ). Recall that z was the last vertex of P , that it was the tail of a vertical blue arc (z, z ′ ) belonging to the model of the arc f . Abusing the notation, we keep the same notation (for z and z ′ ) after all transformations above. Hence, let (i, j) be the coordinates of the last vertex z of P (after modifications). There are different cases depending on the orientation of the last arc of P .

• If the last arc of P was vertical, then the last vertex of P ′ has coordinates (i -1, j). First, we remove (z, z ′ ) from η ′ (f ), and analyse the following cases. * Row j + 1 goes to the right. If z ′ = (i, j + 1) is part of the in-tree of some vertex w ∈ V (D), then add ((i -1, j + 1), (i, j + 1)) to η(w) and let η ′ (f ) = ((i -1, j), (i -1, j + 1)). Otherwise (hence, z ′ had degree two in η(f )), then add ((i -1, j + 1), (i, j + 1)) and ((i -1, j), (i -1, j + 1)) to η ′ (f ). * Row j + 1 goes to the left. First add two new rows between rows j and j + 1, and write the subpath associated to the subdivision of (z, z ′ ) as (z, t, z ′′′ , z ′ ). If z ′ is part of the in-tree of some w ∈ V (D), then add the path (z ′′ , z ′′′ , z ′ ) to η ′ (w) where z ′′′ is the vertex below z ′ and z ′′ is the vertex to the left of z ′′′ , and set η ′ (f ) to be equal to the 2-arc path from the end of P ′ to z ′′ . Otherwise, add the path from the endpoint of P ′ to z ′′ , z ′′′ and z ′ to η ′ (f ). • If the last arc of P was to the left, then the last vertex of P ′ has coordinates (i, j -2). First, remove (z, z ′ ) from η ′ (f ), and add a new column between columns i and i -1. If z ′ = (i, j + 1) is part of the in-tree of some vertex w ∈ V (D), then add (z ′′ , z ′ ) to η ′ (w) where z ′′ is the left neighbor of z ′ and let η ′ (f ) be equal to the 4-arc path from the end of P ′ to z ′′ . Otherwise (hence, z ′ had degree two in η(f )), add the 4-arc path from the end of P ′ to z ′′ and (z ′′ , z ′ ) to η ′ (f ). • If the last arc of P was to the right, then the last vertex of P ′ has coordinates (i, j + 2). Remove the vertical 2-arc path from the end of P to the end of P ′ from η ′ (f ). Note that, right now, Q * n ′ ,2m ′ crosses one more black arc (the first one of P ′ ). However, since P ′ is a path, we may proceed as in the first item to "replace" this black arc by a blue one. Proof. If D has no sources nor sinks, we are done, so suppose otherwise. In what follows, given a source s in D (resp., a sink t), we describe a process that builds a model for an in-arc that we add to s (resp., an out-arc that we add to t), so that the obtained supergraph has also a model in a cylindrical grid and has one less source (resp., sink). By iteratively applying such process, we finish our proof.

Let us consider a butterfly model η of D with a dijoin path P * as in Lemma 1, and suppose that D has a source s (the case of a sink is symmetric). We will add a new arc (z, s) for some z ∈ V (D), and a path Q (finishing in the in-tree of the model of s) for modelling this arc in the existing model η. The difficulty is to find the vertex of an out-tree in which we can start our path Q. First let us add two columns between any two consecutive columns and let us add two rows between any two consecutive rows. We also add one column to the left and one column to the right of the cylindrical grid. The following process is illustrated in Figure 9.

Let r s be the root of η(s). Note that, by assuming η to be minimal (recall Observation 11), we get that the in-tree of the model of s in η is reduced to its root. Let a 1 be the vertex below r s and b 1 the vertex below a 1 . Since we have just added two rows between any two rows, and because the in-tree of s is reduced to r s , we get that a 1 , b 1 are not part of the model of any vertex nor arc. Let Q initially contain just the arc (a 1 , r s ) (this will actually be the last arc of Q). Let us assume that Q has been built up to some vertex a h , i.e., Q = (a h , a h-1 , • • • , a 1 , r s ), and additionally assume that the vertex b h below a h is not part of the model of any vertex nor arc (this is the case for h = 1). Let w be the vertex below b h .

-If w is not part of the model of any vertex nor arc, then let a h+1 = b h and let b h+1 = w, and we continue to build Q; For instance, this is the case in Figure 9 when building the path Q between vertices B and C; -If w is in the out-tree of some vertex, add (w, b h ), (b h , a h ) at the end of Q and we are done.

-If w is part of the in-tree of some vertex a (and not of its out-tree, i.e., w is not the root of the model of a), then assume that the row of a h goes to the right (the other case is symmetric). Let x be the left neighbor of a h , y be the vertex below x (and to the left of b h ) and z the vertex below y (and to the left of w). Note that, since w is part of the model b h is not, then the rows of b h and a h are rows that have been added just before starting the process. In particular, this implies that, either both x and y belong to the model of some e ∈ V (D) ∪ A(D), or neither x nor y is part of any model. In the latter case, we set a h+1 = x and b h+1 = y and go on (for instance, this is the case in Figure 9 when building the path Q between vertices A and B).

Otherwise, we consider the cases:

• x, y are part of the model of a vertex of D. Observe that this implies that the column of x and y cannot be one of the added columns, as such columns cannot have arcs inside any model. Moreover, it implies that w belongs to an added column and so is part of the model of the same vertex as its left neighbor z. Overall, this implies that all x, y, z, w must be part of the model of the same vertex, say a. Recall that the row of a h goes to the right to see that z has out-degree at least 2 in the model of the vertex a. Hence z is in the out-tree of a. This is a contradiction as w is in the in-tree of a, and there cannot be arcs going from the out-tree to the in-tree of any vertex. • x, y are part of the model of an arc of D. In that case, z must be part of the model of the same vertex a as w (because w is part of the model of a vertex and because of the columns added initially). Because x and y belong to added rows, this implies that the arcs (x, y) and (z, y) have the same status, i.e., they are blue arcs. This implies that z is part of the out-tree of a and so w also, a contradiction. -If w is part of the model of some arc e = (u, v) ∈ A(D). Let M be the subpath of η(e) until w. Let us build a path M ′ "parallel" to M as we built a path P ′ parallel to P in the proof of Lemma 1.The first end of M ′ is a vertex of the out-tree of u and its last end w ′ is some neighbor of w. Finally, we add Q ′ , the path from w ′ to a h to Q.

The last two cases allow to ensure that our process will actually terminate. For this purpose, we use the dijoin path P * .

-If (b h , a h ) crosses the dijoin path P * and P * does not cross any blue arc. In this case, let us consider the closest row under P * that contains a vertex of the model. W.l.o.g., let us assume that this row goes to the right and let x be the rightmost vertex of this row that is part of the model of some vertex v * of D. By minimality of the model and because x has no out-neigbour in the model of any vertex or arc, then, x must be the root of η(v * ) (which is actually an in-tree). Now, we add to η(v * ): the up-going arc (x, y) (y being the up-neighbor of x) and the horizontal path Y starting from y to the leftmost vertex of this row (then y becomes the new root of η(v * ) and the path Y will be considered as its out-tree). To conclude this case, add at the beginning of Q, the directed path from the path Y of η(v * ) (added in previous paragraph) to b h . Then, we are done. -If (b h , a h ) crosses P * which crosses some blue arc. Let e be such a blue arc closest to a h and let a = (α, β) ∈ A(D) such that e ∈ η(a). Let us assume that e is to the right of a h (the other case is symmetric). Add at the beginning of Q a path from a left neighbor of e to a h (it might be needed to add to new rows to get the good orientation). For instance, this is the case in Figure 9 when building the path Q between vertices D and C. Hence, our path Q now starts from a left neighbor γ of a vertex of e. As in the fourth item of this proof, let M be the subpath of η(a) which starts from a vertex of the out-tree of α ∈ V (D) until e. Up to adding new rows and new columns, it is possible to add at the beginning of Q a path, "parallel" to M , from a vertex of the out-tree of α to γ. ⊓ ⊔

Fig. 1 :

 1 Fig. 1: The (4 × 4)-grid (left), the (3 × 6)-cylindrical grid C 3,6 (middle), and the directed wall (right) obtained from C 3,6 by removing the three red arcs.

Fig. 2 :

 2 Fig. 2: Two planar digraphs L (left) and R (right) which are not butterfly minors of any cylindrical grid.

Observation 1

 1 Let D = (V, A) be a plane digraph, and e ∈ A be any arc of D. Then, (D \ e) * = D * /e * and (D/e) * = D * \ e * .

i i + 1 (

 1 Adding 1 column between i and i + 1 in (a).(c) Adding 2 rows between j and j +1 in (b).

Fig. 4 :

 4 Fig.4: Green rows and columns are added. Blue arcs belong to the images of some arcs of G by η. Grey subtrees (with black vertices and arcs) are the images of some vertices of G by η.

Fig. 5 :

 5 Fig.5: Construction of D P * (s, t). On the left, a dijoin path P * is represented by dashed red arcs. On the right, the obtained digraph D P * (s, t) is depicted.

Theorem 4 .

 4 Let D = (V, A) be a digraph without sources or sinks. If D has a planar embedding such that D * admits a dijoin path P * , then D has a butterfly model in C n,2m for some n, m ∈ N * .

Observation 9 A

 9 plane digraph D is strong if and only if D * is a DAG. Given a digraph D = (V, A) and e ∈ A, recall that D \ e is the digraph (V, A \ {e}), and that D/e is the digraph obtained from D after contracting the arc e. The following result is obvious. Observation 1 Let D = (V, A) be a plane digraph, and e ∈ A be any arc of D. Then, (D \ e) * = D * /e * and (D/e) * = D * \ e * .

Observation 11

 11 If a graph G has a model in some graph H, then G has a minimal model in H.

Theorem 4 .

 4 Let D = (V, A) be a digraph without sources or sinks. If D has a planar embedding such that D * admits a dijoin path P * , then D has a butterfly model in C n,2m for some n, m ∈ N * .

Fig. 6 :

 6 Fig. 6: Constructing a model from a visibility representation of a DAG.

⊓ ⊔ Lemma 1 .

 1 If a digraph D has a butterfly model η in C n,2m , then D has a butterfly model in C n ′ ,2m ′ for some n ′ ≥ n and m ′ ≥ m such that no black arcs of this model are dual of an arc of Q * n ′ ,2m ′ .

Fig. 8 :

 8 Fig. 8: Construction of P ′ (visualized by the red line in (b)) from P (drawn in red in (a)). In (b), lines and columns highlighted in green are added lines and columns.

  The added rows and columns are depicted in green. The model Q of the added in-arc to the source s is the dotted blue line. Note that Q actually uses the "free space", i.e., the added rows and columns.

Fig. 9 :

 9 Fig. 9: Illustration of the process in the proof of Lemma 2.

  and let P ′ i = P i-1 otherwise. By Observations 1 and 4, P ′ i is a dijoin walk of G * i and, by Observation 6, G * i admits a dijoin path P i . If s i consists in removing an isolated vertex, then, by Observation 5,P i = P i-1 is a dijoin path of G * i .And if s i is a butterfly contraction of the arc e i ∈ A(G i-1 ), where e * i / ∈ A(P i-1 ), then Observations 1 and 3 ensure us that P i = P i-1 is a dijoin path of G * i . So, finally, let us consider the case when s i consists in butterfly contracting an arc e

  The next lemma states that if a digraph D has a model in a cylindrical grid, then it is possible to get a model such that Q * n,2m only crosses blue arcs of this model. Lemma 1. If a digraph D has a butterfly model η in C n,2m , then D has a butterfly model in C n ′ ,2m ′ for some n ′ ≥ n and m ′ ≥ m such that no black arcs of this model are dual of an arc of Q * n ′ ,2m ′ .

Lemma 2. If a digraph D = (V, A) has a butterfly model in C n,2m , then D has a spanning supergraph with neither sources nor sinks that has a butterfly model in C n ′ ,2m ′ for some n ′ ≥ n and m ′ ≥ m. Sketch of the proof. If D has no sources nor sinks, then we are done, so suppose otherwise.

  Therefore, we reach a new model where Q * n ′ ,2m ′ still crosses k black arcs, the leftmost one being part of the out-tree of v and such that the new T v has only k ′ -1 blue arcs with tail in it. ⊓ ⊔ Lemma 2. If a digraph D = (V, A) has a butterfly model in C n,2m , then D has a spanning supergraph with neither sources nor sinks that has a butterfly model in C n ′ ,2m ′ for some n ′ ≥ n and m ′ ≥ m.

Here, segment means line segment in the plane.


LES CRITÈRES FORMELS COMME ÉLÉMENT D'ÉVALUATION QUALITATIVE DES MONOGRAPHIES LIMITES ET DÉRIVES

Mehenni Akbal, Université d'Alger 2 (campus de Bouzaréah).

Fatima Chebab, Université d'Alger 2 (campus de Bouzaréah).

Résumé

Le présent article est une réflexion ouverte. Son objectif est de contribuer à ouvrir des pistes de recherche en discutant une pratique largement répandue dans les bibliothèques : celle qui consiste à évaluer qualitativement, à des fins d'acquisition, dans le cadre du développement des collections, les monographies sur la base de critères formels. Par critères formels d'une monographie, il faut comprendre l'ensemble des indications descriptives et informatives qui sont inhérentes à sa forme plutôt qu'à son contenu

-Introduction

Les éléments, qui entourent la monographie 1 et la prolongent dans l'acte éditorial, ont été au coeur des préoccupations de nombreux chercheurs appartenant à différents horizons. Ils constituent un terrain de recherche d'une extrême richesse qui fait appel à la pluridisciplinarité. En effet, de nombreuses approches relevant de plusieurs disciplines y sont applicables : littérature, sociologie, psychologie, sciences de l'information et de la communication, bibliologie, documentologie, bibliothéconomie, médiologie, etc.

Nous devons à Gérard Genette, dans une étude relevant de la théorie littéraire, le concept de « paratexte » [Genette, G. ; 1987] 2 qui regroupe les pratiques et les discours souvent hétéroclites et disparates émanant de l'auteur et/ou de l'éditeur. Il s'agit de paratexte situé à l'intérieur du livre, appelé le péritexte, (le titre, les sous-titres, les intertitres, l'auteur, l'éditeur, la date d'édition, le préfacier, le postfacier, les notes, les illustrations, la table des matières, la quatrième de couverture, …) et celui situé à l'extérieur du livre, désigné l'épitexte, (entretiens et interviews donnés par l'auteur avant, après et/ou pendant la publication de son oeuvre, sa correspondance, …). De son côté, Brigitte Ouvry-Vial a tenté, selon une approche médiologique, une esquisse d'une construction théorique de l'acte éditorial, baptisée « théorie du geste » [Ouvry-Vial, B. ; 2007] 3 .

Notre propos n'est pas de critiquer, d'adhérer ou d'étayer ces thèses. Il s'agit plutôt pour nous de discuter une pratique largement répandue dans les bibliothèques : celle qui consiste à évaluer qualitativement, à des fins d'acquisition, les monographies sur la base de critères formels dont la définition, perçue sous un angle différent, ne correspond pas à celles qui sont précédemment exposées. En d'autres termes, l'objectif que nous nous assignons est de discuter la validité théorico-méthodologique d'une telle démarche pour en relever les limites et les dérapages.

Le présent article est donc une réflexion ouverte. Il n'a pas du tout une dimension pratique à même d'offrir au bibliothécaire-documentaliste gestionnaire d'un organisme documentaire de recherche un outil pouvant lui permettre de formuler une problématique et de définir une politique de collecte de la production scientifique monographique.

-Les fondements théoriques de l'étude

Pour définir ce qu'est un critère formel d'une publication monographique, nous nous sommes référés à deux textes qui relèvent, peu ou prou, des sciences de l'information et de la communication. Ces deux textes, qui font autorité, sont au coeur des fondements théoricométhodologiques de notre étude. Le premier est un des premiers textes de l'école de Palo Alto 4 : Une Logique de la communication [Watzlawick, P. et al. ; 1972]. Le second est de Bruno Latour [1985]: Les Vues de l'esprit.

-1 -Premier texte

S'inscrivant dans le courant pragmatique, la contribution de l'école de Palo Alto est inestimable pour l'ouverture paradigmatique du champ des études relevant des sciences de l'information et de la communication. Une Logique de la communication 5 en est le texte fondateur. Recelant l'essentiel de son apport, ce texte offre des outils et des instruments d'une importance capitale.

En effet, dans le deuxième chapitre de cet ouvrage, se trouvent formulées des « propositions pour une axiomatique de la communication » qui, bien que forgées dans un contexte micro, trouvent leur plus haute signification et un terrain d'application dans un contexte macro. Il s'agit de : « 1 -L'impossibilité de ne pas communiquer. 2 -Les niveaux d'analyse de la communication : contenu et relation. 3 -La ponctuation de la séquence des faits.4 -La distinction entre la communication digitale et la communication analogique. 5 -L'interaction symétrique et complémentaire ».

Arrêtons-nous à la deuxième proposition. Elle signifie, comme le précise si bien les représentants de l'école de Palo Alto que « toute communication présente deux aspects : le contenu et la relation, tels que le second englobe le premier et par suite est une métacommunication ». Elle met en évidence, dans toute « action de communication » 6 , la prédominance de la forme sur le contenu, de l'apparence sur la signifiance. Roman Jakobson [1963] 7 considère ce concept de relation comme un des facteurs de la communication. A ce facteur, il fait correspondre une fonction qu'il nomme « phatique ». Elle permet de provoquer et de maintenir le contact entre le destinateur et le destinataire (entre l'émetteur et le récepteur).

--Deuxième texte

Pour Bruno Latour [1985], « l'énoncé à la fois accepté, stable, répandu et approprié est une rareté. Comment le rendre plus fréquent ? Il faut à la fois intéresser un plus grand nombre de gens à sa construction, pour que l'énoncé se répande, et rendre le comportement de ceux qui le saisissent entièrement prévisible, pour qu'il ne soit pas déformé ou trahi. Les deux conditions sont évidemment contradictoires : si l'on intéresse beaucoup de gens, c'est en s'approchant au plus près de leurs lubies, passions et croyances, il sera donc d'autant plus difficile d'empêcher qu'ils ne transforment ou discutent profondément l'énoncé. D'un autre côté, si personne n'est intéressé ou enrôlé, l'énoncé ne bougera pas d'un centimètre, demeurant dans la tête de son locuteur un rêve, une lubie, une folie. La difficulté deviendra presque insoluble si le locuteur veut convaincre d'un fait nouveau qui va contre l'intérêt et les croyances d'un grand nombre de gens ». Pour Bruno Latour, la raison n'est pas une cause mais un effet. Les énoncés scientifiques relèvent des rapports de force, souvent largement établis et fortement configurés, des énonciateurs. L'action de faire admettre et de valider un énoncé scientifique passe, nécessairement non sans ardeur, dans les conduites forcées de l'harmonie et du conformisme. L'énonciateur doit lutter contre des adversaires, faire appel à des alliés, etc. La dispute, la persuasion et la conviction sont les leitmotivs d'une telle action. Naissent de ceux-là ceux-ci : des mouvements de convergences et de solidarité. La vérité n'est donc pas intérieure à l'énoncé mais extérieure. Philippe Breton [1992] considère à raison que nous sommes « tout entier à l'extérieur » 8 .

Soutenir une thèse et la faire admettre par les autres ne sont rien d'autres, selon Bruno Latour, qu'une construction sociale dans la mesure où elle se confine à une affaire de recrutement, d'associations, de « médiations » 9 , de relations et de réseaux 10 . Cette thèse à son tour est tenue de répondre à ce précieux tissage en s'y ajustant et en s'y adaptant.

Un énoncé, que personne ne cautionne en le reprenant à son compte ou en le cosignant et auquel adhésion fait défaut, tombe en désuétude dans le monde du bruit ou dans celui du silence 11 , car il est loin d'obéir, originellement et par essence, au « grand partage » 12 soutenu par l'ethnologue Jack Goody.

Ces deux textes (Une Logique de la communication et Les Vues de l'esprit) constituent le socle théorique qui a servi à la fois de prétexte et de justification pour définir cette notion de critère formel et de source d'inspiration pour mener notre réflexion.

-3 -Définition d'un critère formel

Le bibliothécaire-documentaliste s'appuie, pour évaluer qualitativement une monographie, sur deux types de critères : Les critères inhérents au contenu et les critères formels. Parmi les critères inhérents au contenu, il convient de recenser : le titre, le texte de la préface, le texte de la postface, le résumé, les mots-clés et le texte intégral. Le titre pose quelques problèmes au point où il nous laisse parfois dubitatifs et perplexes. En effet, pour chaque oeuvre, qu'elle soit littéraire ou scientifique, il y a un titre. Un titre qui rend, généralement, compte du texte en résumant en quelques mots son contenu. Il est à ce dernier ce que représente un curriculum vitae à un homme en quête d'un emploi. C'est du titre que dépend, en partie, l'impact qu'aura l'oeuvre sur le public. Formel, en revanche, renvoie à toute démarche « qui considère la forme, l'apparence plus que le contenu ». Qui considère l'extériorité plus que l'intériorité.

Par critères formels d'une publication monographique scientifique donc, il faut comprendre l'ensemble des indications descriptives et informatives qui sont inhérentes à sa forme plutôt qu'à son contenu. Quels sont ces critères ? En réponse, il convient de citer : l'auteur, le préfacier, le signataire de la postface, les indications portant actes de rencontres scientifiques, les références bibliographiques, l'éditeur, la collection, l'institution de financement, les illustrations, le matériel d'accompagnement, le nombre de pages, l'année d'édition et enfin le format.

Les pratiques bibliothéconomiques intègrent graduellement ces critères formels pour les ériger au rang de critères d'évaluation qualitative des monographies.

-Les critères formels : Limites et dérives

Les critères formels que nous retenons pour discussion sont les suivants : le signataire de l'oeuvre, le préfacier, le postfacier, la mention portant « actes de rencontres scientifiques », la bibliographie. Ils présentent la caractéristique d'avoir l'humain comme dénominateur commun. 15 . Ce qui en découle : la difficulté, voire l'impossibilité, de dissocier l'énoncé de son énonciateur.

-1 -L'auteur : L'autorité et la notoriété

S'imposer auprès de tous comme incontournable, servir de règle et de référence dans un domaine donné, faire autorité, exercer un ascendant, incarner l'excellence, avoir de la notoriété relèvent de la reconnaissance plutôt que de la connaissance. Il s'agit de témoignages qui sont extérieurs à l'auteur et à son énoncé. Ce sont là les paramètres d'évaluation les plus courants des « qualités », du mérite et de la notoriété d'un auteur.

Nous sommes tentés, dans ce contexte, de reproduire le schéma édifiant d'explication psychologique de la racine du pouvoir d'Etienne de La Boétie : « Chose vraiment surprenante ! C'est de voir des millions et des millions d'hommes, misérablement asservis, et soumis tête baissée, à un joug déplorable, non qu'ils y soient contraints par une force majeure, mais parce qu'ils sont fascinés et, pour ainsi dire, ensorcelés » [La Boétie, E. de ; éd. 1978] [START_REF] Boétie | Discours de la servitude volontaire, précédé et suivi de La Boétie et la question du politique[END_REF] . Ici, la simple force physique est loin d'expliquer les fondements et les secrets du pouvoir. Ce dernier se confine dans une machination psychologique très complexe dont le moteur est la fascination et l'ensorcellement. Citant Pierre Bourdieu, qui considère que « l'arbitraire est aussi au principe de tous les champs, même les plus purs, comme les mondes artistiques ou scientifiques », Odile Riondet estime que « ce qui est dit « beau » n'est pas une oeuvre qui rejoint un sentiment universel de plénitude, mais ce que des groupes sociaux sont parvenus à imposer comme objet d'admiration » [Riondet, O. ; 2003] 17 . Reste la question de savoir si la notoriété d'un auteur est liée à la totalité de son oeuvre ou aux textes dits fondateurs au terme desquels il s'est fait un nom en construisant une théorie, un modèle, un schéma ou en forgeant un paradigme ou un concept.

C'est pour cette raison qu'il convient de distinguer dans l'oeuvre d'une vie entre ce qui est original et ce qui est redondant. A cela s'ajoute, « l'exploitation de la situation sociale de l'auteur par l'éditeur » relevée pertinemment par Abraham A. Moles qu'il explique par le fait qu'« un nombre très appréciable d'auteurs d'ouvrages (…) ont des fonctions sociales en rapport avec les ouvrages qu'ils écrivent : c'est le cas type des universitaires ou chercheurs » [Moles, A.

A. ; 1980] [START_REF] Moles | Le Livre et les éditeurs[END_REF] . Ce qui donne naissance à une production parfois abondante mais démunie d'originalité.

-2 -Le préfacier : La quête d'une caution intellectuelle

Par définition, une préface est un texte plus ou moins court qui ouvre un ou d'autres textes. Elle peut s'assigner plusieurs objectifs : rendre compte brièvement du texte intégral en le présentant ou en offrant un apport supplémentaire d'informations, de justifications et/ou d'explications ; appuyer la thèse développée par l'auteur ; susciter la curiosité du lecteur pour l'inciter à poursuivre la lecture du texte ; désigner et cerner le lectorat ciblé.

La composition d'un texte liminaire -qui sert à fixer le texte et le contexte de sa composition dans un cadre spatio-temporel, à faire l'annonce de sa thématique, à montrer son intérêt et sa portée scientifiques, etc.est une tâche que l'auteur peut prendre en charge luimême ou qu'il peut confier à un de ses paires.

Les faits nous révèlent, dans la majeure partie des cas, une autre réalité qui cette fois n'est guidée que par le désir de l'auteur de relever ou de soutenir le niveau de son texte par le prestige et la renommée du signataire de la préface.

L'auteur requiert un préfacier, dont les propos ne contredisent que très rarement les siens, pour une caution intellectuelle. Pour faire valider son oeuvre, il doit, en guise de protection, se procurer un parapluie ou se trouver une ombre censé lui offrir sécurité et postérité.

Le recours à un préfacier n'est pas un geste anodin, innocent et neutre. Cette pratique, qui est assimilable à une ruse énonciative, obéit beaucoup plus à une logique intersubjective qu'objective.

--Le postfacier : Un avis émérite ou fantaisiste

Si la préface est composée en vue de déclore un ou des textes, la postface, en revanche, sert à, le ou les, clore. C'est de cette place justement qu'elle tient, à raison, son appellation. Cependant, deux motivations peuvent présider au recours à une postface :

Dans le cas où elle est faite, dans une autre langue que celle de l'auteur, non sans objectivité et avec une grande liberté de propos, pour exposer le bilan du travail réalisé, en relevant ses points forts et ses faiblesses, et pour proposer des pistes et des voies de recherche et d'investigation ultérieures, elle portera, à coup sûr, tous ses attributs et ses fondements originels. On dira, dans ce cas, que c'est un avis émérite qui ne peut pas ne pas être le bienvenu.

Dans le cas contraire, on dira qu'elle est fantaisiste et démunie d'une quelconque résonance cognitive. Elle est comme cette eau-de-vie qui est fabriquée pour imiter le kirsch ; alors que le kirsch a sa saveur et ses propriétés. C'est, en substance, dans la problématique mimétique, largement et pertinemment élucidée par le célèbre chartiste René Girard [START_REF] Girard | Mensonge romantique et vérité romanesque[END_REF] , que se trouvent fournies, d'une façon salutaire, les réponses théoriques à cette autre forme de communication dont, l'absence parfois angoisse et, la présence menace car, servant d'ornement et de décor, elle n'incarne qu'une force corruptrice du lecteur et n'obéit qu'à une démarche conspiratrice dont le galbe est formé par une série de verbes, à savoir, reconnaître, connaître, fasciner, embarquer et enfin enfermer. Michel Serres explique ce dilemme autrement. Citons : « Devenir plusieurs, [Serres, M. ; 1991] [START_REF] Serres | Le Tiers-instruit[END_REF] . Cette forme d'exposition à l'Autre restreint nos champs d'action et de déambulation. Elle tue en nous la création.

braver l'extérieur, bifurquer ailleurs. Voici les trois premières étrangetés, les trois variétés d'altérité, les trois premières façons de s'exposer. Car il n'y a pas d'apprentissage sans exposition, souvent dangereuse, à l'autre. Je ne saurai jamais plus qui je suis, où je suis, d'où je viens, où je vais, par où passer. Je m'expose à autrui, aux étrangetés »

-4 -Les actes de rencontres scientifiques : La quête de l'unanimisme ou du consensus

Par rencontres scientifiques, il faut comprendre les congrès, les colloques ou les réunions savantes où sont présentées des communications ou des exposés relatifs à des thématiques spécifiques qui rendent compte des derniers résultats de la recherche. Ces communications sont, à l'issue, présentées sous forme de monographie.

Dans ce genre de rencontres, le participant est censé obéir à la logique des idées et des mots. Souventes fois, il tient compte de la logique des forces et des connivences. C'est comme un nageur, ou un navigateur, il se doit de connaître la des courants ou des vents. Car nager contre le courant n'est guère facile mais est parfois nécessaire. Alors que le bon nageur n'a pas d'a priori, nager à contre courant n'est pas une facilité, mais, dans certains cas une nécessité. On revient à un autre axiome de l'école de Palo Alto : « communiquer, c'est entrer dans l'orchestre. Un orchestre dont chacun fait partie et où tout le monde joue suivant une partition invisible déjà élaborée » [Bateson, G. ; 1981] [START_REF] Bateson | La Nouvelle communication, textes recueillis et présentés par Yves Winkin[END_REF] . Cet axiome, dont la seule vérité est la négation de la vérité, explique le gigantesque emprisonnement provoqué par la tendance nécessaire à toujours se conformer pour être en harmonie avec les autres. Naissent de ce conformisme : un mensonge communicationnel, un travestissement de la pensée et un pastiche multiforme que nourrissent et maintiennent, à souhait et à merci, le croire et le faire croire. Ce qui en découle : une attitude qui consiste à tirer parti des circonstances en les utilisant au mieux, en se prêtant à des accommodements, en faisant des concessions, en manquant de rigueur, en transigeant au besoin avec ce que l'homme a de plus cher, son authenticité et son originalité.

A cela, il convient d'ajouter le fait que ces rencontres n'obéissent pas toujours à un pluralisme paradigmatique. Car les démarches sont perverties, voire obnubilées, par des intérêts corporatifs et bureaucratiques ou par des réseaux de connivences. Le problème persiste et persistera dès lors que les problématiques sont déterminées par des programmes et des slogans politiques fabriqués par des idéologues rêveurs.

Ces rencontres elles-mêmes supposées le cadre idéal d'où émerge l'originalité participent du coup à renforcer grandement cette tendance à l'uniformité. Les maîtres, « prisonniers et otages d'un système de représentation bien déterminé » (Octave Hamelin), ayant subi eux-mêmes un enseignement réducteur enseignent à leurs disciples, plutôt qu'une ouverture (pluralisme paradigmatique), l'art facile de la convenance, de l'uniformité et du conformisme. Le disciple apprend son métier de disciple qui fera de lui cet être capable de la meilleure insertion. Pour obtenir les grâces de la reconnaissance, le disciple apprend à coproduire, à cosigner et à restituer l'enseignement du maître. Sortir de l'ornière est souvent perçu comme une atteinte flagrante à « l'ordre naturel des choses », à l'intégrité de cette organisation où se moulent les cerveaux qui « guideront le monde ».

Tout cela laisse penser que l'originalité est synonyme d'anticonformisme.

-5 -Les références bibliographiques : La quête d'abri

Savoir l'existence d'une bibliographie à la fin de la monographie, y jeter un oeil pour prendre connaissance des textes qui la composent et de leur mode de présentation sont des gestes quasi-machinaux qu'accomplit le bibliothécaire-documentaliste dans l'opération de choix et de sélection des ouvrages à acquérir.

Les textes scientifiques sont bardés de référence. Car faire référence aux autres ou citer les autres traduit une manière tout indiquée de faire valoir une idée, une logique ou une démarche en la raccordant à celle des autres, surtout si ces derniers jouissent déjà d'une audience et/ou d'un crédit. Le cas de la pétition est suffisamment dans le contexte. Son initiateur s'arrange pour recueillir d'abord les signatures de personnalités célèbres (scientifiques de tous bords, artistes, écrivains, etc.) avant de la soumettre au reste de la population.

L'analyse des citations, dont les fondements théoriques sont bien débrouillés par Derek John de Solla Price [Garfield, E. ; 1985] [START_REF] Garfield | In Tribute to Derek John de Solla Price[END_REF] dans son modèle bibliométrique, rend compte de la structure sociocognitive de la science.

G. N. Gilbert [1977] [START_REF] Huisman | Le Dire et le faire. Pour comprendre la persuasion. Propagande, publicité, relations publiques[END_REF] . Pour ne prendre que l'exemple des sciences de l'information et de la communication, Abraham A. Moles, dans la préface qu'il a consacrée à l'ouvrage de Claude E. Shannon et Warren Weaver, Théorie mathématique de l'information, remarque que ce texte « a été universellement cité en tête de bibliographies de tous ceux qui de près ou de loin se trouvent toucher à la théorie de l'information, à la fois à titre de caution (et quelque fois d'abri), au titre de rigueur, au titre de référence intellectuelle » [cf. C. E. Shannon et W. Weaver, trad. fse. ; 1975] 25 .

Si nous nous référons au constat fait par Abraham A. Moles, il nous est possible de relever les trois hypothèses de travail des études relatives à l'analyse des citations ; à savoir, l'usage, le mérite et l'excellence. L'objectif étant d'étudier les fréquences avec lesquelles les documents sont cités et de les répartir dans des grilles d'analyse et d'interprétation. Quels sont les documents cités ? Les moins cités ? Pourquoi ? Y a-t-il un schéma général à ce phénomène ? Telles sont les questions de base qui constituent les problématiques des études relatives à l'analyse des citations.

Si le mérite et l'excellence ne posent a priori aucun problème, l'usage, par contre, est source de dérives et de dérapages surtout lorsqu'il est sous-tendu par des motivations conventionnelles et conformistes.

A ces critères formels, il convient d'énumérer d'autres qui bien que ne se rapportant pas à l'humain provoquent performativement par la simple alchimie de les lire ou de les entendre des attitudes et des décisions insoupçonnées chez le bibliothécaire-documentaliste. Il s'agit de :

-La maison d'édition : la réputation et la ligne éditoriale.

-La collection : l'orthodoxie et la renommée.

-L'institution de financement et sa vocation.

A ceux-là, il convient d'ajouter ceux-ci : -Les illustrations et leurs origines.

-Le(s) matériel(s) d'accompagnement.

-Le nombre de pages.

-L'année d'édition.

-Le format.

Conclusion

Les critères formels obéissent quelque part à la même logique que celle du message publicitaire qui a pu transcender le mensonge et la tromperie en un moyen terriblement efficace de persuasion. Le mensonge élaboré se transforme dès lors en technique de communication. Il fait partie de cet empire sémiotique où « to do things with words » [Austin, J. L. ; 1962] 26 préside à nos comportements, à nos modes de vie et de pensée. C'est-à-dire, un empire où l'on agit par des mots sur les choses. L'empire où « on fait l'opinion » [Champagne, P. ; 1990] [START_REF] Champagne | Faire l'opinion[END_REF] . Car, « il n'échappe à personne qu'écrire c'est prescrire ; instruire, conduire ; transmettre, soumettre » [Debray, R. ; 1980] [START_REF] Debray | Le Scribe. Genèse du politique[END_REF] .

L'univers graphique est celui d'un subtil pastiche. Et, ce mimétisme-là donne naissance à une pollution typographique qui entraîne le bibliothécaire-documentaliste vers un labyrinthe de difficultés et d'embarras. En attestent, tous les Introduction à, les Synthèse de, les Précis de, les Ce qu'il faut savoir sur, les Tout savoir sur, … produits quotidiennement dans toutes les disciplines à des quantités incommensurables. En d'autres termes, la foisonnante production scientifique, signée par des innombrables compilateurs de tous bords, encombre les textes originaux et authentiques. Ces imitateurs et ces suiveurs, malgré leur parfaite connaissance des exigences et des contraintes de la recherche scientifique, versent dans une étouffante redondance qui ne permet pas au lecteur non averti d'accéder aux travaux originaux des authentiques créateurs dont le nombre, contrairement à ce que nous laissent croire les bibliographies qui closent les thèses universitaires, est très réduit. Le bibliothécaire-documentaliste, de son côté, éprouve les pires difficultés pour sélectionner la totalité de l'essentiel de cette production.

Enfin, pour clore notre réflexion, une note d'espoir s'impose. Nous rêvons d'une bibliothèque scientifique idéale dont la politique de collecte de la documentation est fondée sur deux principes : l'exhaustivité et l'originalité (c'est-à-dire n'acquérir que la totalité de la production scientifique originale).

La construction d'un tel modèle [START_REF] Akbal | Typologie du savoir[END_REF] ne peut être envisagée sans une lecture alerte, minutieuse et réfléchie du texte de Thomas Samuel Kuhn : La Structure des révolutions scientifiques [START_REF] Kuhn | La Structure des révolutions scientifiques. Titre original The Structure of Scientific Revolutions[END_REF] .

  Il convient de distinguer, cependant, entre le titre d'une oeuvre littéraire ou artistique et le titre d'une oeuvre scientifique. Hypothétiquement parlant, le titre d'une oeuvre littéraire ou artistique est polysémique. Il est construit en vue d'impressionner au lieu d'inspirer, d'accrocher au lieu de décrocher, d'attacher au lieu de détacher, d'éblouir au lieu d'émoustiller. Par contre, le titre d'une oeuvre scientifique est monosémique. Souvent, c'est de sa longueur que dépend sa monosémie. Plus il est long mieux ça vaut. Qu'entendons-nous, par contre, par critères formels ? Le Petit Robert : Critère (1750) est un mot d'origine latine. Criterium, du grec Kritêrion, de Krinein. Il signifie « discerner ». Discerner, c'est « porter sur un objet un jugement d'appréciation ». Apprécier n'est rien d'autre qu'évaluer.

  David Pontille a bien débrouillé la notion de l'auteur scientifique et cellede la signature scientifique. A la question « qu'est-ce qu'un auteur scientifique ? », il répond : c'est le créateur d'une oeuvre originale non libre de droits [Pontille, D. ; 2006] 13 . Il considère, dans un autre texte, que la signature scientifique est d'une extrême importance dans la mesure où elle « déborde largement le cadre des activités scientifiques. Le monde de l'art et de la littérature, mais aussi le monde économique sont traversés par son hégémonie croissante : la consommation de tel produit plutôt que tel autre est dans bien des cas attachée au nom autant qu'au bien. Cette présence de la signature dans la production-consommation des biens culturels est essentielle. Elle souligne une dimension marchande à laquelle les pratiques scientifiques pourraient bien être assujetties : le(s) nom(s) propre(s) attaché(s) aux énoncés semble fonctionner de plus en plus comme des marques commerciales » [Pontille, D. ; 2002] 14 . Ce qui équivaut au concept de « site d'énonciation » forgé par Pierre Bourdieu. Dans Ce que parler veut dire, il note que « les discours ne sont pas seulement (ou seulement par exception) des signes destinés à être compris, déchiffrés ; et sont aussi des signes de richesse destinés à être évalués, appréciés et des signes d'autorité destinés à être crus et obéis » [Bourdieu, P. ; 1982]

  [START_REF] Gilbert | Referencing as Persuasion[END_REF] , dans un article qu'il a publié depuis déjà une bonne trentaine d'années, est parvenu à la conclusion suivante : faire référence aux autres augmente le pouvoir de persuasion chez les lecteurs. Citer un maître fondateur d'une théorie, d'un modèle, d'un schéma, d'un paradigme ou d'un concept vous protège comme « le manteau de Dieu ». Dans son livre Le Dire et le faire, DenisHuisman [1983] remarque que « la communication persuasive est un acte social élaboré, à partir des tourbillons emphatiques dans lesquels nous sommes plongés en commun avec d'autres »

Renvois bibliographiques

1 Une monographie est un livre scientifique spécialisé. Le livre est un type de document. Le document étant un objet matériel préfabriqué qui supporte une production intellectuelle. Le Petit Robert : Crée, au XIIe siècle, du latin documentum qui signifie « ce qui sert à instruire ». Sous le vocable monographie, il convient d'exclure les publications en séries. Il s'agit donc de toute publication qui obéit au circuit éditorial et présente une unité matérielle et intellectuelle. On y trouve les monographies : à un seul auteur, à plusieurs auteurs, les collectifs et les actes de rencontres scientifiques.