Hazel Everett

Sylvain Lazard

Giuseppe Liotta
email: liotta@diei.unipg.it

Stephen Wismath
email: wismath@uleth.ca

Universal Sets of n Points for One-bend Drawings of Planar Graphs with n Vertices *

This paper shows that any planar graph with n vertices can be point-set embedded with at most one bend per edge on a universal set of n points in the plane. An implication of this result is that any number of planar graphs admit a simultaneous embedding without mapping with at most one bend per edge.

Introduction

Let S be a set of m distinct points in the plane and let G be a planar graph with n vertices (n m). A point-set embedding of G on S is a planar drawing of G such that each vertex is drawn as a point of S and the edges are drawn as polylines. The problem of computing point-set embeddings of planar graphs has a long tradition both in the graph drawing and in the computational geometry literature (see, e.g., [START_REF] Gritzmann | Embedding a planar triangulation with vertices at specified points[END_REF][START_REF] Kaufmann | Embedding vertices at points: Few bends suffice for planar graphs[END_REF][START_REF] Pach | Embedding planar graphs at fixed vertex locations[END_REF]). Considerable attention has been devoted to the study of universal sets of points. We say that a set S of m points is h-bend universal for a family of planar graphs with n vertices (n m) if each graph in the family admits a point-set embedding onto S that has at most h bends along each edge.

Gritzman, Mohar, Pach and Pollack [START_REF] Gritzmann | Embedding a planar triangulation with vertices at specified points[END_REF] proved that every set of n distinct points in general position in the plane is 0-bend universal for the class of outerplanar graphs with n vertices. De Fraysseix, Pach, and Pollack [START_REF] De Fraysseix | How to draw a planar graph on a grid[END_REF] and independently Schnyder [START_REF] Schnyder | Embedding planar graphs on the grid[END_REF] proved that a grid with O(n 2 ) points is 0-bend universal for all planar graphs with n vertices. De Fraysseix et al. [START_REF] De Fraysseix | How to draw a planar graph on a grid[END_REF] also showed that a 0-bend universal set of points for all planar graphs having n vertices cannot have n + o( √ n) points. This last lower bound was improved by Chrobak and Karloff [START_REF] Chrobak | A lower bound on the size of universal sets for planar graphs[END_REF] and later by Kurowski [START_REF] Kurowski | A 1.235 lower bound on the number of points needed to draw all n-vertex planar graphs[END_REF] who showed that linearly many extra points are necessary for a 0-bend universal set of points for all planar graphs having n vertices. On the other hand, if two bends along each edge are allowed, a tight bound on the size of the point-set is known: Kaufmann and Wiese [START_REF] Kaufmann | Embedding vertices at points: Few bends suffice for planar graphs[END_REF] proved that every set of n distinct points in the plane is 2-bend universal for planar graphs with n vertices. Finally, if one bend along each edge is allowed, Di Giacomo et al. [START_REF] Di Giacomo | Curve-constrained drawings of planar graphs[END_REF] proved a related result that every planar graph can be drawn with its vertices on any given convex curve; however, the positions of the points on the curve depend on the planar graph.

In this paper we study the cardinality of a universal set of points for all planar graphs with n vertices under the assumption that at most one bend per edge is allowed in the point-set embedding. We prove the following theorem.

Theorem 1 Let F n be the family of all planar graphs with n vertices. There exists a set of n distinct points in the plane that is 1-bend universal for F n .

The proof is constructive; an example is shown in Figure 1. We define a set S of n points (Figure 1(a)) and show how to compute in O(n) time an embedding of any planar graph with n vertices on S such that the resulting drawing has at most one bend per edge. The drawing procedure starts by computing a special type of book embedding defined in Section 2 (see Figure 1(c)) and then uses this book embedding to construct the point-set embedding with the algorithm described in Section 3 (see Figure 1(d)).

Our universal set of n points can be defined either (i) on an integer grid of size n2 n by n or (ii) with algebraic coordinates such that they are the vertices of a convex chain with unit-length edges. In the former case, the graphs can be drawn with all bend-points also on the grid points of the n2 n by n grid. In the latter case, all planar graphs of F n can be drawn with all bend-points and vertices in a square of size n by n at distance at least 1 2(d+1) apart, where d is the maximum degree of the graph. Furthermore, relaxing the unit edge length constraint, a universal set of points can be chosen on any given convex curve.

We conclude this introduction by noting a result that is immediately implied by Theorem 1. Two planar graphs G 1 and G 2 with the same set of vertices are said to admit a simultaneous embedding without mapping if there exists a set of points in the plane that supports a point-set embedding of both G 1 and G 2 [START_REF] Braß | On simultaneous planar graph embeddings[END_REF]. 1 It is not known whether any two planar graphs admit a simultaneous embedding without mapping such that all edges are straight-line segments. However, Brass et al. [START_REF] Braß | On simultaneous planar graph embeddings[END_REF] showed that any planar graph has a straight-line simultaneous embedding without mapping with any number of outerplanar graphs. Kaufmann and Wiese [START_REF] Kaufmann | Embedding vertices at points: Few bends suffice for planar graphs[END_REF] also proved that any two planar graphs have a simultaneous embedding without mapping such that each edge is drawn with at most two bends. In this context, Theorem 1 fills the gap for the one-bend case and implies the following.

Corollary 2 Any number of planar graphs with n vertices admit a simultaneous embedding without mapping with at most one bend per edge.

The paper is organized as follows. In Section 2, we first introduce some notation and review preliminary results about topological book embeddings. We then prove Theorem 1 in Section 3; we first present, in Section 3.1, a construction of sets of n points in convex position, called necklaces and describe, in Section 3.2, an algorithm that computes a 1bend point-set embedding of any planar graph with n vertices on a necklace of n points. We then prove the correctness of the algorithm in Section 3.3 before concluding in Section 4.

(b) (a) (c) (d) v 7 v 3 v 2 v 1 v 0 v 7 v 6 p 0 p 1 p 2 p 3 r 5 v 6 v 3 v 2 v 1 p 7 p 6 p 5 p 4 r 0 r 1 r 2 r 3 r 4 w 4 w 2 w 3 w 5 w 1 w 0 w 7 v 5 v 4 v 0 w 6 w 7 w 5 w 6 w 4 w 2 w 3 w 1 w 0 v 5 v 4

Topological Book Embeddings

In this section, we review the notions of monotone, proper, and augmented topological book embeddings (see e.g., [START_REF] Di Giacomo | Curve-constrained drawings of planar graphs[END_REF][START_REF] Enomoto | Embedding graphs into a three page book with o(m log n) crossings of edges over the spine[END_REF]). We start with preliminary notation.

Consider the Cartesian coordinate system (O, x, y) and let p, q be two points in the plane. We say that p is left of q and we denote it as p < q if the x-coordinate of p is less than the x-coordinate of q; we shall also use the notation p q to mean that either p is left of q or p coincides with q; we define similarly p > q and p q. Let pq denote the line segment from p to q.

A spine is a horizontal line. Let ℓ be a spine and let p, q be two points on ℓ. Let p < q and let b be a point on the perpendicular bisector of pq and not on ℓ. An arc (p, q) with bend-point b consists of segments pb and bq; points p and q are respectively the left and right endpoint of (p, q). Arc (p, q) can be either in the half-plane above the spine or in the half-plane below the spine (such half-planes are assumed to be closed sets); in the first case we say that the arc is in the top page of ℓ, otherwise it is in the bottom page of ℓ.

Let G = (V, E) be a planar graph. A monotone topological book embedding of G [START_REF] Di Giacomo | Curve-constrained drawings of planar graphs[END_REF], denoted Γ, is a planar drawing such that all vertices of G are represented as points of a spine ℓ and each edge is either represented as an arc in the bottom page, or as an arc in the top page, or as a polyline that crosses the spine and consists of two consecutive arcs. More precisely, let (u, v) be an edge of a monotone topological book embedding that crosses the spine at a point d; assuming that u is left of v along the spine, (u, v) is such that (see Figure 2): (i) u < d < v, (ii) arc (u, d) is in the bottom page, and (iii) arc (d, v) is in the top page. Point d is called the spine crossing of (u, v) and is also denoted as d(u, v).

Di Giacomo et al. [START_REF] Di Giacomo | Curve-constrained drawings of planar graphs[END_REF] presented a constructive proof of the existence of monotone topological book embeddings. They also presented an algorithm to prove that any planar graph admits a one-bend drawing with all vertices on any given convex curve. Their algorithm can be viewed as follows. First, a monotone topological book embedding is constructed. Second, the spine is deformed into a convex curve while moving the vertices on the curve so that the bends in the bottom page straighten, resulting in a one-bend drawing. More precisely, the vertices and incident edges are added, one by one, to the drawing according to a canonical ordering; the position of a vertex thus depends on the position of the vertices and edges drawn in previous steps. In our approach, we carefully choose the position of the vertices on a convex curve and prove that the edges of any planar graph can then be drawn by a technique similar to that of Di Giacomo et al. [START_REF] Di Giacomo | Curve-constrained drawings of planar graphs[END_REF] on that point set. Since monotone topological book embeddings are crucial in our construction, we sketch here, for completeness, the constructive proof of their existence.

Theorem 3 ([5]) Every planar graph admits a monotone topological book embedding which can be computed in linear time in the size of the graph.

Sketch of Proof.

We describe an algorithm that takes a planar embedding of a maximal planar graph (every planar graph can be augmented to become maximally planar) and produces a linear ordering of its vertices and spine crossings for its edges. This linear ordering defines a monotone topological book embedding of the input graph.

Let G be a maximal embedded planar graph with n vertices and let w 0 , w 1 , w n-1 denote the vertices of its outer face. A monotone topological book embedding of G is constructed by adding a single vertex per step. The algorithm chooses the next vertex to be added by following a canonical ordering [START_REF] De Fraysseix | How to draw a planar graph on a grid[END_REF] of G. A canonical ordering of G with respect to edge (w 0 , w 1 ) is an ordering of the vertices w 0 , w 1 , w 2 , . . . , w n-1 of G such that for every integer k (3 k < n) the following properties hold (see Figure 1(b)):

• The embedded subgraph G k-1 ⊆ G induced by w 0 , w 1 , . . . , w k-1 is biconnected and the external boundary C k-1 of G k-1 contains edge (w 0 , w 1 ); • w k is a vertex (of G \ G k-1 ) in the external face of G k-1 , and its neighbors in G k-1 form a subpath of the path C k-1 \ {(w 0 , w 1 )}.
Now, let w 0 , w 1 , w 2 , . . . , w n-1 be a canonical ordering of G. At Step i, 0 i < n, the algorithm processes vertex w i and all edges from w i to some w j<i . All edges are drawn with a spine crossing (that is, as a concatenation of an arc in the bottom page and one in the top page). Also, the monotone topological book embedding Γ i computed at the end of Step i (2 i < n) satisfies the following invariants:

1. Γ i is a monotone topological book embedding of G i that preserves the embedding of G i .

2. For every pair of vertices u and v that are consecutive on the path C i \ {(w 0 , w 1 )} (2 i < n) there is no vertex or spine crossing between u and d(u, v) in the linear ordering of Γ i . In the first three steps of the algorithm, vertices w 0 , w 1 , w 2 , and the division vertices of the edges between them are placed so that the linear ordering is the following: w 0 , d(w 0 , w 2 ), w 2 , d(w 2 , w 1 ), d(w 0 , w 1 ), w 1 (see Figure 3(a)). Notice that the two invariants hold at the end of third step. The vertex to be placed at Step i is

u ′ u v v ′ (a) u u ′ v v ′ (b) v = v ′ u u ′ (c)
w i (3 i < n); let u 1 , u 2 , . . . , u h be the neighbors of w i in G i-1
. By Invariant 2, there is no vertex or spine crossing between u 1 and d(u 1 , u 2 ). Vertex w i and all the division vertices d(w i , u j ) (1 j h) are placed between u 1 and d(u 1 , u 2 ) in such a way that their order is u 1 , 3(b)). At the end of Step n -1, the computed linear ordering defines a monotone topological book embedding of G. That the running time of the algorithm is linear in the size of the graph is straightforward.

d(u 1 , w i ), w i , d(w i , u h ), d(w i , u h-1 ), . . . , d(w i , u 2 ), d(u 1 , u 2 ) (see Figure
Let G = (V, E) be a planar graph, let Γ be a monotone topological book embedding of G computed according to Theorem 3, let (u, v) be an edge of Γ, and let d be its spine crossing. Also (see Figure 2), let u ′ be the rightmost vertex along the spine of Γ such that u ′ < d and let v ′ be the leftmost vertex of the spine of Γ such that d < v ′ . We say that u ′ and v ′ are the two bounding vertices of d. We say that d is a proper spine crossing if its bounding vertices u ′ and v ′ are such that u < u ′ < d < v ′ < v. A monotone topological book embedding is proper if all of its spine crossings are proper. Since an edge that crosses the spine with a non-proper spine crossing can be replaced by a single arc (in the top or in the bottom page) without introducing an intersection, we directly obtain the following lemma from Theorem 3.

Lemma 4 Every planar graph has a proper monotone topological book embedding which can be computed in linear time in the size of the graph.

Let now Γ be a proper monotone topological book embedding of a planar graph G. If we insert a dummy vertex for each spine crossing of Γ, we obtain a new proper topological book embedding Γ ′ such that Γ ′ represents a planar subdivision G ′ of G obtained by splitting with a vertex some of the edges of G. We call the graph G ′ an augmented form of G and the drawing Γ ′ an augmented proper topological book embedding of G.

A vertex of G ′ that is also a vertex of G is called a real vertex of Γ ′ ; a vertex of G ′ that corresponds to a spine crossing of Γ is called a division vertex of Γ ′ . Note that every division vertex of Γ ′ has degree two and that every edge of Γ ′ is either an arc in the top page or an arc in the bottom page. The bounding vertices of a division vertex d of Γ ′ are the two real vertices that form the bounding vertices of the spine crossing corresponding to d in Γ. The following property is a consequence of the planarity of Γ ′ (see Figure 4). Property 1 Let (u, v) and (u ′ , v ′ ) be two distinct arcs of Γ ′ that are in the same page and such that u Figure 5: Three consecutive points of a necklace: p i+2 lies in the grey region defined by p i and p i+1 . In (b), given p i+2 and p i+1 on a convex curve, p i is chosen on the curve such that the grey region it defines (with p i+1 ) contains p i+2 .

< u ′ . Then, (i) u < v u ′ < v ′ or (ii) u < u ′ < v ′ v.

Proof of Theorem 1

We prove Theorem 1 by first defining a family of sets of n points in convex position, called necklaces (Section 3.1), and then by describing an algorithm that computes a 1bend point-set embedding of any planar graph with n vertices on a necklace of n points (Section 3.2). We prove the correctness of the algorithm, and thus Theorem 1, in Section 3.3.

Necklaces

Refer to Figure 5(a) and to Figure 1(a) for a complete example. Let p 0 be any point on the x-axis strictly left of the vertical y-axis and p 1 be any point strictly in the top-left quadrant of p 0 . We construct p i+2 , for 0 i n -2, from p i and p i+1 as follows. Let r i be the projection of p i on the vertical y-axis. Point p i+2 is chosen anywhere on or below the line through r i and p i+1 and strictly above the horizontal line through p i+1 . Let S be any set of n points defined by the above procedure; we call S a necklace of n points. We observe that, if we allow the points to have real (algebraic) coordinates, we can choose p i+2 on the line through r i and p i+1 such that p i+1 is equidistant to p i and p i+2 . Then it is straightforward that if the distance between p i and p i+1 is 1 for all i, then all points lie in a square of size n by n. Notice also that we can construct a necklace, with algebraic coordinates, on any convex curve. Indeed, given any convex arc, we can choose the y-axis and the points p n-1 , . . . , p 0 , in that order, such that p i is the point on the curve whose projection on the y-axis lies on the tangent to the curve at p i+1 (see Figure 5(b)). 2We can alternatively place the vertices on grid points as follows. Consider p 0 and p 1 at (-1, 0) and (-2, 1), respectively, and let p i+2 be chosen as the symmetric point of r i with respect to p i+1 . Then, it is straightforward that p i has coordinates (-2 i , i), for i 0.

Computing 1-bend point-set embeddings

We describe a drawing algorithm, called 1-Bend Universal Drawer or 1-BUD for short, that takes as input a planar graph G with n vertices and a necklace S of n points and returns a point-set embedding of G on S such that every edge of G is drawn with at most one bend.

Before describing our algorithm, we introduce the notion of bend-lines and vertical strips (see Figure 6(b)). The bend-line of p i (i > 1) is the horizontal segment from p i-1 to r i-1 . The vertical strip of p i (i < n -1), denoted V (p i ), is the strip bounded by the vertical lines through p i and p i+1 ; the strip is considered open on the left side and closed on the right side. Denote also by CH(S) and ∂CH(S) the convex hull of S and its boundary.

The algorithm consists of the following steps.

Step 1: Draw the vertices of G. Compute a proper monotone topological book embedding Γ of G and the corresponding augmented proper topological book embedding Γ ′ (see Section 2). Let ℓ be the spine of Γ ′ . Label the real vertices of Γ ′ (that is, the vertices of Γ) on ℓ by v n-1 , . . . , v 0 in that order from left to right, i.e., v i < v i-1 (see Figure 1(c)). Modify Γ ′ so that every edge connecting two consecutive real vertices is drawn as an arc in the bottom page. Map every real vertex v i to point p i of the necklace (see Figure 1(d)).

Step 2: Draw the bends of the arcs of the top page of Γ ′ . Refer to Figure 6(a). For every real vertex v i of Γ ′ , let a i0 , a i1 , • • • , a ik be the sequence of arcs in the top page of Γ ′ whose right endpoint is v i ; assume that a i0 , a i1 , • • • , a ik are encountered in this order when going counterclockwise around v i by starting the tour from a point on ℓ slightly to the right of v i . Let w i j denote the left (real or division) vertex of a i j in Γ ′ (0 j k). If w i j is a real vertex of Γ ′ (such as w i0 in Figure 6(a)), it is also labeled as vertex v h i j for some 0 h i j n -1. Otherwise, w i j is a division vertex of Γ ′ (such as w i1 in Figure 6(a)) and we define h i j such that v h i j and v h i j -1 are the two bounding real vertices of w i j in Γ ′ . Refer now to Figure 6(b). For each arc a i j , we draw the bend of a i j at a point q i j on the bend-line of p h i j (i.e., through p h i j -1 ) such that (i) q i0 lies on the vertical ray above p i and, for j > 0, (ii) q i j lies strictly to the right of the vertical line through p i+1 , and strictly to the left of the line through p i and q i( j-1) .

Step 3: Draw the division vertices of Γ ′ . With the notation of Step 2, for each division vertex w i j of Γ ′ , let (v k i j , w i j ) be the arc Γ ′ whose right endpoint is w i j (see Figure 6(a)). Draw w i j at the intersection point, p w i j , between segment p k i j q i j and ∂CH(S) (see Figure 6(b)). (Note that, as will show in Lemma 6, p w i j is not a point of the necklace {p 0 , . . . , p n-1 }.)

Step 4: Draw the arcs of Γ ′ . For each arc (u, v) of Γ ′ , let p u , p v be the points representing u and v along ∂CH(S). If (u, v) is an arc in the bottom page, draw it as the chord p u p v . For instance, arc (v k i1 , w i1 ) in Figure 6(a) is drawn as chord p k i1 p w i1 in Figure 6(b).

If (u, v) is an arc in the top page of Γ ′ , let q be the point computed at Step 2 that represents the bend-point of (u, v). Draw (u, v) as the polyline consisting of segments p u q and qp v . For instance, arc a i0 = (w i0 , v i ) in Figure 6(a) is drawn as the polyline consisting of p h i0 q i0 and q i0 p i in Figure 6(b) and arc a i1 = (w i1 , v i ) is drawn as p w i1 q i1 and q i1 p i .

Step 5. Let Γ be the drawing computed in Steps 1 to 4. The final drawing of G is obtained by ignoring the division vertices in Γ.

Note that, in

Step 2, we can trivially draw all the bends on integer grid points if there are n grid points between p i and p i+1 on any horizontal line. Hence, all bends can be drawn on integer grid points if the necklace consists of point p 0 with coordinates (-1, 0) and points p i with coordinates (-n 2 i-1 , i), for i > 0. Similarly, if a necklace consists of the vertices (with algebraic coordinates) of a convex chain with unit-length edges, the bend-points can be drawn in Step 2 such that the horizontal distance between every consecutive pair of points of a sequence p i , q i0 , . . . , q ik , p i+1 is at least the horizontal distance between p i and p i+1 times 1 d+1 where where d is the maximum degree of the graph. 3 Furthermore, if the necklace is constructed such that the horizontal distance between p 0 and p 1 (and thus between any p i and p i+1 ) is at least 1 2 , then all the bend-points and vertices lie in a square of size n by n at distance at least 1 2(d+1) apart. Proving Theorem 1 amounts to showing that the above algorithm correctly computes a point-set embedding of G on S such that each edge has at most one bend. The idea is to prove that the drawing computed at the end of Step 5 maintains the topology of Γ and that the geometric properties of the proper monotone topological book embedding and of the necklace implies a point-set embedding of the graph without edge-crossings and with at most one bend per edge. This proof is the subject of the next section.

v k i2 v h i1 = v h i2 v k i1 w i2 w i1 v i v h i1 -1 = v h i2 -1 a i2 a i1 a i0 w i0 = v h i0 (a) r h i1 -1 strip V (p i ) p h i0 -1 r h i0 -1 bend-line of p h i0 bend-line of p h i1 q i1 q i2 p k i2 p k i1 p w i1 p w i2 p i+1 p i q i0 p h i1 p h i1 -1 p h i0 (b)

Proof of correctness

We use here the same notation as in the previous section. We prove in this section the following main lemma which directly yields the correctness of the algorithm (Theorem 5). Main Lemma. Γ is a planar drawing.

Based on this lemma we prove the correctness of the algorithm.

Theorem 5 Algorithm 1-BUD computes a 1-bend point-set embedding of a planar graph with n vertices on a necklace with n points.

Proof. Observe that every real vertex of Γ ′ is drawn as a point of S in Γ. Since Γ does not have edge crossings (Main Lemma), removing the division vertices (which are of degree two) from Γ gives a point-set embedding of G on S. Also, by construction, the two edges incident on a division vertex of Γ form a flat angle, and thus removing the division vertices from Γ does not increase the number of bends. It follows that the drawing computed by Algorithm 1-BUD is a point-set embedding of G on S such that each edge has at most one bend.

We now prove the Main Lemma. We start with three preliminary lemmas. We then prove, in different cases depending on which page two arcs of Γ ′ lie, that their drawings in Γ do not cross.

Let a = (u, v) and a ′ = (u ′ , v ′ ) be two arcs of Γ ′ such that u u ′ and let p u , p v , p u ′ , and p v ′ be the points of Γ representing u, v, u ′ , and v ′ , respectively. Recall that if u is a real vertex of Γ ′ then p u is a point of the necklace S = {p 0 , . . . , p n-1 }, otherwise, u is a division vertex of Γ ′ and p u is not a priori a point of the necklace; similarly for v, u ′ and v ′ .

Lemma 6 If u is a division vertex of Γ ′ whose bounding vertices are v t and v t-1 , then p

t < p u < p t-1 . u v v t-1 b v h v t (a) p h p v p t q p u p t-1 r t-1 (b)
Figure 7: Illustration for Lemmas 6, 7 and 8 for the case where u is a division vertex (otherwise, p u = p t and p h is not relevant).

Proof. Refer to Figure 7. Let (v h , u) and (u, v) be the two arcs of Γ ′ incident to u that lie, respectively, in the bottom page and top page of Γ ′ . Since Γ ′ is a proper monotone topological book embedding, we have that

v h < v t < u < v t-1 < v. Both v h < v t
are real vertices of Γ ′ and they are thus mapped to p h < p t , respectively, in Step 1 of the algorithm. In Step 2, the bend of arc (u, v) is drawn as a point of the bend-line of p t , denoted as q.

The division vertex u is drawn in Step 3, as the intersection point, p u , between segment p h q and ∂CH(S). Since q lies on the relatively-open segment p t-1 r t-1 and p h lies (i) strictly below the line through p t and r t-1 , (ii) strictly above the line through p t-1 and r t-1 , and (iii) strictly to the left of the line through p t and p t-1 , the point p u lies on the relative interior of segment p t p t-1 . Hence, p t < p u < p t-1 .

Lemma 7

If arc a = (u, v) is in the top page of Γ ′ such that its bend is drawn in Γ on the bend-line of p t , then v t u < v t-1 v and p t p u < p t-1 p v .

Proof. First, note that v is a real vertex of Γ ′ since a is in the top page. It directly follows from Step 2 of the algorithm that u is either equal to v t or is a division vertex of Γ ′ whose bounding vertices are v t and v t-1 . In the former case, u = v t < v t-1 v and since they are all real vertices, Step 1 implies p u = p t < p t-1 p v . In the latter case, we have v t < u < v t-1 < v (since Γ ′ is an augmented proper monotone topological book embedding) and, by Lemma 6, p t < p u < p t-1 furthermore, since v t-1 < v are both real vertices, we also have p t-1 < p v .

Lemma 8

If arc a = (u, v) is in the top page of Γ ′ , it is drawn in Γ as a polyline joining p u to p v with one bend-point q such that q (and thus the whole polyline) lies below the horizontal line through p u and above the horizontal line through p v .

Proof. The bend of a is drawn on the bend-line of, say, p t (that is on the horizontal line through p t-1 ). By Lemma 7, p u < p t-1 p v and thus p t-1 is below the horizontal line through p u and above the horizontal line through p v , hence the result.

Lemma 9 If a = (u, v) and a ′ = (u ′ , v ′ ) are in the top page of Γ ′ such that u < u ′ and their bends are drawn in Γ on the same bend-line, then their drawings in Γ do not intersect, except possibly at a common endpoint. Furthermore, p u < p u ′ . Proof. Refer to Figure 8. Let q and q ′ be the bends of a and a ′ in Γ, respectively, and assume that q and q ′ are drawn on the bend-line of p t . By Lemma 7, we have

q ′ r t-1 p v p t-1 p v ′
u ′ < v t-1 and v t-1 v, thus u ′ < v. Property 1 thus implies that (ii) u < u ′ < v ′ v (see Figure 4(b-c)).
We first show that q ′ is to the left of q, i.e. q ′ < q. Points q and q ′ are in the vertical strips V (p v ) and V (p v ′ ), respectively (see Step 2)

. Recall that v ′ v in Γ ′ . If v ′ < v in Γ ′ ,
we have that p v ′ < p v since both v and v ′ are real vertices. Then, since any point in V (p v ′ ) is to the left of any point in V (p v ), point q ′ is to the left of q. Otherwise, v = v ′ and both q and q ′ are inside V (p v ). In this case, consider the arcs incident to vertex v = v ′ of Γ ′ and visit them by going counterclockwise around v (start the clockwise tour at a point on the spine of Γ ′ slightly to the right of v). Since u < u ′ and Γ ′ is planar, we have that arc (u ′ , v ′ ) is encountered after arc (u, v) (see Figure 4(c)). Hence, Step 2 implies that q ′ is to the left of q on the bend-line of p t .

Segments p u q and p u ′ q ′ do not intersect each other. By Lemma 7, v t u < v t-1 and v t u ′ < v t-1 . Thus, if u (resp. u ′ ) is a real vertex, it is equal to v t . Note also that at most one of u and u ′ can be equal to v t (since u = u ′ ). Thus, if u ′ is a real vertex, [START_REF] Bernhart | The book thickness of a graph[END_REF] and thus p u = p t = p u ′ ; Lemma 7 then implies that p u = p t < p u ′ < p t-1 . Thus, points p u , p u ′ , q ′ , and q appear in that order on the polyline formed by segments p t p t-1 and p t-1 r t-1 (as in Figure 8 except that, here, p u = p t ). Therefore, segments p u q and p u ′ q ′ do not intersect each other. Note that we have also proved that p u < p u ′ .

u ′ = v t < u < v t-1 , contradicting the fact that u < u ′ . Otherwise, if u is a real vertex, u = v t < u ′ < v t-
We now consider the case where u and u ′ are both division vertices of Γ ′ . In this case, we have v t < u < u ′ < v t-1 . Let (v h , u) and (v h ′ , u ′ ) be the two arcs in the bottom page of Γ ′ incident to u and u ′ . Since Γ ′ is an augmented proper monotone topological book embedding, v h < v t and v h ′ < v t . Furthermore, since Γ ′ is a planar drawing, we have v h ′ v h < v t < u < u ′ . Finally, since v h ′ , v h , and v t are real vertices of Γ ′ , we have p h ′ p h < p t (by Step 1).

Since q ′ < q both lie on the bend-line of p t and p h ′ p h < p t , the segments p h q and p h ′ q ′ do not intersect each other, except possibly at p h = p h ′ (see Figure 8). Since p u (resp. p u ′ ) lies by construction (see Step 3) on segment p h q (resp. p h ′ q ′ ), segments p u q and p u ′ q ′ do not intersect each other. Furthermore, since p u and p u ′ also lie on segment p t p t-1 (by Lemma 7) and q ′ < q, points p u , p u ′ , q ′ , and q appear in that order on the polyline formed by segments p t p t-1 and p t-1 r t-1 , we have p u < p u ′ .

The drawings of a and a ′ in Γ do not intersect, except possibly at p v = p v ′ . If v = v ′ , the vertical strips V (p v ) and V (p v ′ ) are disjoint and, since they contain q and q ′ , respectively, segments qp v and q ′ p v ′ do not intersect. On the other hand, if v = v ′ , segments qp v and q ′ p v ′ intersect only at their common endpoint p v = p v ′ since they are not collinear by construction (see Step 2).

Finally, segment p u q (resp. p u ′ q ′ ) does not intersect segments q ′ p v ′ (resp. qp v ) because they are separated by the bend-line containing q and q ′ (by Lemma 8) and q = q ′ . Therefore, the drawings of arcs a and a ′ in Γ do not intersect each other except possibly at

p v = p v ′ .
Before proving that the drawings of a and a ′ in Γ do not cross each other in the other cases, we prove that the left-to-right order along the spine of Γ is preserved along ∂CH(S).

Lemma 10 If u < u ′ in Γ ′ , then p u < p u ′ .
Proof. We consider different cases depending on whether u and u ′ are real or division vertices.

Case (i): both u and u ′ are real vertices. Step 1 of the algorithm assigns to u a label with index larger than that of u ′ and thus it maps u to a point of the necklace with index larger than that of u ′ . Hence, by construction of the necklace, the point p u representing u in Γ is to the left of the point p u ′ representing u ′ in Γ.

Case (ii): u is a division vertex and u

′ is a real vertex. Let v t and v t-1 be the two bounding vertices of u in Γ ′ ; we have v t < u < v t-1 . Since u ′ is a real vertex such that u < u ′ , we have v t-1 u ′ . It thus follows from Step 1 that p t-1 p u ′ and Lemma 6 implies p u < p u ′ .

Case (iii): u is a real vertex and u ′ is a division vertex. A symmetric argument as above gives the result.

Case (iv): both u and u ′ are division vertices. Let v t < v t-1 be the bounding vertices of u and v t ′ < v t ′ -1 the bounding vertices of u ′ in Γ ′ . If these pairs of bounding vertices do not coincide then, since u < u ′ , we have v

t < u < v t-1 v t ′ < u ′ < v t ′ -1 .
Step 1 then implies that p t < p t-1 p t ′ < p t ′ -1 . Also, Lemma 6 implies that p t < p u < p t-1 and p t ′ < p u ′ < p t ′ -1 , thus p u < p u ′ . On the other hand, if the pairs of bounding vertices coincide (i.e., t = t ′ ), then the bends of two arcs (u, v) and (u ′ , v ′ ) in the top page of Γ ′ are both drawn on the bend-line of p t and Lemma 9 implies that p u < p u ′ .

We now resume proving that the drawings of a and a ′ do not cross each other.

Lemma 11 If a = (u, v) and a ′ = (u ′ , v ′ ) are in the top page of Γ ′ such that u < u ′ and their bends are drawn in Γ on distinct bend-lines, then their drawings in Γ do not intersect, except possibly at a common endpoint.

Proof. Let q and q ′ be the bends of a and a ′ in Γ and assume that they lie on the bend-lines of p t and p t ′ , respectively, with t = t ′ . Property 1 implies that (i) u < v u ′ < v ′ or (ii) u < u ′ < v ′ v. We consider the two cases separately.

Lemmas 9, 11, 12, 13, and 14 imply that no two edges of Γ intersect, except possibly at common endpoints. This concludes the proof of the Main Lemma that the drawing Γ is planar because, by Lemma 10, all the vertices of Γ ′ are mapped to distinct vertices on the boundary of CH(S).

Conclusion

This paper shows that there exists a set S of n distinct points in the plane such that every planar graph with n vertices admits a point-set embedding onto S where every edge is drawn as a polyline having at most one bend. Moreover, such a universal set S can be constructed on any convex curve. An application of this result to the simultaneous embeddability problem without mapping is also described.

We remark that our result closes gap about universal sets of points for planar graphs. Indeed, it was already known that a universal set of (exactly) n points supporting straightline drawings of planar graphs does not exist [START_REF] Chrobak | A lower bound on the size of universal sets for planar graphs[END_REF][START_REF] De Fraysseix | How to draw a planar graph on a grid[END_REF][START_REF] Kurowski | A 1.235 lower bound on the number of points needed to draw all n-vertex planar graphs[END_REF], while any set of n points can be universal if two bends per edge are allowed [START_REF] Kaufmann | Embedding vertices at points: Few bends suffice for planar graphs[END_REF]. Also, notice that not all sets of points can be 1-bend universal: for example, if the points of S are collinear, exactly the family of sub-hamiltonian planar graphs has a 1-bend point-set embedding on S [START_REF] Bernhart | The book thickness of a graph[END_REF]. However, it is an open problem to determine whether any strictly convex point set is 1-bend universal.

When the vertices (and possibly the bend points) are required to lie on a regular grid, our construction of universal point-sets for one-bend drawing of planar graphs uses grids of exponential size (in the size of the graph). Moreover, if both the vertices and the bend points are to be drawn on a regular grid, the angle between adjacent incident edges may be exponentially small. We leave as an open problem to find a universal point-set for one-bend drawing of planar graphs in a polynomial-size regular grid and such that the minimum angle between adjacent incident edges of the drawings is at least (inversely) polynomial in the size of the graph.

Figure 1 :Figure 2 :

 12 Figure 1: (a) A universal set, S, of 8 points, p 0 , . . . , p 7 . (b) A graph G with 8 vertices. (c) A proper monotone topological book embedding, Γ, of G. The vertices are labeled both by their labels in graph G and drawing Γ. (d) The drawing, Γ, of G on the universal point set S.

Figure 3 :

 3 Figure 3: Construction of a monotone topological book embedding.

Figure 4 :

 4 Figure 4: Illustration for Property 1.

Figure 6 :

 6 Figure 6: Illustration for Algorithm 1-Bend Universal Drawer. (a) Part of an augmented proper monotone topological book embedding. (b) Sketch of the corresponding drawing on the necklace. Points p k i1 and p k i2 are much farther to the left than shown.

Figure 8 :

 8 Figure 8: Illustration for Lemma 9.

A simultaneous embedding is said to be with mapping if the same vertex is mapped to the same point in both the drawings of G 1 and of G

[START_REF] Braß | On simultaneous planar graph embeddings[END_REF].

In other words, p n-1 , . . . , p 0 is the sequence of points obtained by applying Newton's root-finding method starting from p n-1 (the y-axis plays here the role of the x-axis in Newton's method).

Note that q i0 should then be drawn strictly inside the strip V (p i ) instead of vertically above p i .

* Research supported by NSERC and the MIUR Project "MAINSTREAM: Drawing and Computational Geometry", Bertinoro, Italy, March 2007.

Case (i) u < v u ′ . Refer to Figure 9(a). By Lemma 8, arc a is drawn above the horizontal line through p v and arc a ′ is drawn below the horizontal line through p t ′ . Moreover, by Lemma 7,v

and, by Lemma 10, p v p t ′ . Thus p v is above, or equal to, p t ′ and the drawings of a and a ′ in Γ do not intersect, except possibly at a common endpoint.

Thus, by Lemma 10,

In particular, we have p t-1 p u ′ thus (by Lemma 8) segment p u q, which is above the bend-line (of p t ) through p t-1 , is above p u ′ , which is also above the drawing of a ′ in Γ (by Lemma 8). Hence p u q does not intersect the drawing of a ′ , except possibly at q = p u ′ . If q = p u ′ , then q lies on ∂CH(S) and thus q = p t-1 . In Step 2 of the algorithm, q is drawn at p t-1 only in the case when p t-1 = p v , which contradicts (1). Hence, segment p u q does not intersect the drawing of a ′ in Γ.

As in the proof of Lemma 9, the two segments qp v and q ′ p v ′ do not intersect except at

Thus the drawings of a and a ′ in Γ can only intersect at p v = p v ′ or at an intersection point between segments qp v and

The drawings of a and a ′ then have distinct endpoints and thus intersect an even number of times (since q = q ′ as they lie on distinct bend-lines). Since there is at most one possible intersection point (between the two segments qp v and p u ′ q ′ ), the drawings of a and a ′ in Γ do not intersect.

and the planarity of Γ ′ imply that the arc a ′ is encountered (in Γ ′ ) before a when going clockwise around v = v ′ by starting the tour from a point on the spine ℓ slightly to the left of v = v ′ (see Figure 4(c)). Thus, by Step 2, q ′ is drawn on a ray (from p v = p v ′ ) that is to the left of the ray supporting q. Moreover, since segment p u ′ q ′ is drawn to the left of the ray supporting q ′ , p u ′ q ′ does not intersect segment qp v . Hence the drawings of a and a ′ intersect only at their common endpoint

Lemma 12 If a = (u, v) and a ′ = (u ′ , v ′ ) are in the top page of Γ ′ such that u = u ′ , then their drawings in Γ only intersect at their common endpoint p u = p u ′ .

Proof. The bends of arcs a and a ′ are drawn at two distinct points q and q ′ that lie on the same bend-line and that lie in the vertical strips V (p v ) and V (p v ′ ), respectively (see Step 2). The arcs a and a ′ are drawn as polylines that of segments p u q, qp v and p u ′ q ′ , q ′ p v ′ . The two segments p u q and p u ′ q ′ intersect only at their common endpoint p u = p u ′ and they do not properly intersect with the two other segments since they are separated by the bend-line containing q and q ′ (by Lemma 8). Also the two segments v and q ′ p v ′ do not intersect since they lie, respectively, in the two vertical strips V (p v ) and V (p v ′ ) which are distinct (indeed v = v ′ since u = u ′ ) and do not intersect by construction. Therefore, the drawings of arcs a and a ′ intersect only at p u = p u ′ .

Lemma 13 If a and a ′ are in the bottom page of Γ ′ , their drawings in Γ do not intersect, except possibly at a common endpoint.

Proof. Arc a is drawn as segment p u p v and a ′ as segment p u ′ p v ′ (see Step 4). By Property 1, either (i

In all cases, Lemma 10 and the convexity of S imply that p u p v and p u ′ p v ′ do not intersect each other, except possibly at a common endpoint.

Lemma 14 If a and a ′ are in opposite pages of Γ ′ , their drawings in Γ do not intersect, except possibly at a common endpoint.

Proof. Assume that a = (u, v) is in the bottom page of Γ ′ and that a ′ = (u ′ , v ′ ) is in the top page.

The arc a is drawn as a chord in CH(S). If v is a division vertex of Γ ′ with bounding vertices v t < v t-1 , then u < v t < v (since Γ ′ is an augmented proper monotone topological book embedding); thus p u < p t < p v (by Lemma 10) and a is drawn as a chord strictly inside CH(S) (except for its endpoints). Otherwise, v is a real vertex of Γ ′ and thus, both p u and p v are vertices of CH(S). Hence, a is drawn as a chord strictly inside CH(S) (except for its endpoints) or it is drawn as an edge of CH(S).

On the other hand, arc a ′ is drawn as a polyline joining p u ′ to p v ′ with bend-point q ′ . Since p u ′ and p v ′ lie on the boundary of CH(S) and q ′ lies strictly outside CH(S) (see Step 2), the arc a ′ is drawn, in Γ, strictly outside CH(S), except for its endpoints. Thus, if a is drawn strictly inside CH(S) (except for its endpoints), the drawings of a and a ′ do not intersect, except possibly at a common endpoint.

Suppose now that a is drawn as an edge of CH(S). Then the drawings of a and a ′ do not intersect, except possibly at a common endpoint, unless p u ′ lies on the relative interior of the edge p u p v of CH(S). In that case, u ′ is a division vertex of Γ ′ whose bounding vertices are u and v (by Lemma 7); thus (u, v) cannot be an arc of Γ ′ (since Γ ′ is an augmented proper monotone topological book embedding). Hence, the drawings of a and a ′ do not intersect, except possibly at a common endpoint.


Anne-Françoise Sch

Joevenn Neo

Alice Rekab

Tony Yanick

Invention en philosophie et silence du futur

Course description

This seminar is concerned with redefining the relationship of the future within the domains of philosophy, arts, and sciences. We will study how the future is not only a temporal lapse, supposed to occur after the past and the present, but above all a modality capable of intervening in the present. If the perspective of our future no longer depends on forthcoming developments of the present, then we will acquire a more intimate knowledge of the unknown that will introduce changes in our present.

Invention is implicitly motivated by the call of the future. But this is an imagined future, inchoative, with snatches and sketches of images, time and places; a general idea that motivates invention. These fragments of the future, partly unknown and never completely given, are what allows one to inhabit space and time, and to find its individuation among others: The future that often gives rise to apocalyptic or science-fiction narratives is one already determined and received from the outside. However, the kind of future that stimulates invention is not engaged with existing narratives, but with the diversity of modes of invention of the disciplines themselves, as well as of the imagination and fiction peculiar to them. Invention cannot be separated from the future, but this is a future that resists narration, and which, from this point of view, contains a driving charge of silence.

The seminar is both a review of existing literature regarding the connections between philosophy, arts, sciences, the future, and fiction: a forum for generating new associations between the realms.

Throughout the seminar, students will work individually and collaboratively to work on practical exercises concerning the following:

Consideration of the future does not depend on any discipline and it can be apprehended by each. We propose exercises of philosophical invention, of which we will give elements of methods, from future developed by the students according to their discipline of origin and/or their activity.

Course Aims and Objectives

AIMS

• To create dialogue and superpositions of Future(s) in the virtual space of the classroom.

• To manifest interpretations of the Future in the present not as a Philosophy of the Future but as an Operator for Fiction in the present moment. • To generate a collaborative atmosphere and a democracy of disciplinary knowledges amongst students and instructors. • To emphasis practice and discussion

We attempt to transpose the temporal idea of the future, the most commonly understood and the most used, into a spatial idea, where it becomes silent, but dynamic. It is not a question of denying the future as time, but of apprehending it also as a mode (& as a mood). It then functions as a break to reinterpret the parameters of our world. It differs from the future with which it is often confused, the latter assuming on the contrary a continuity between the present and what is supposed to happen. We will show more secret effects of the future, as sources of unknown, asymmetries and inequalities, interdisciplines, sources of injunctions without slogans, and especially serpentine line ("linea serpentinata") well known in art, theology and philosophy.

We will show how a generic epistemology makes room for the future in science. We will explore this in the philosophical and artist registers as well.

We will see that the future reverses the causalities (there is no biology of the future, even if predictive biologies are drawn, but there is a future-biology, when it is combined with other disciplines or disciplines, mathematical modeling, computer science, material sciences, etc).

We will then put the subject in a systematic relation with the glossary of epistemology distributed for the occasion, with the objective of showing that the future increases the dimensions of objects and contemporary problems, but in a non-rigid way, by breaking them down unexpectedly into integrative objects scientific philosophical artistic disciplines, and by suggesting new regimes of invention.

The seminar is composed of eight two and a half hour sessions, each of which will be conducted as an extended seminar. Readings will be set for each week, and students will be expected to write 400 words on some aspect of the week's topic in advance. During this period material written by the participants about the previous week will be discussed alongside the set material. Both the reading list and the student's responses will be posted to the google classroom page for everyone to read and comment on, providing some preliminary threads for the group discussion. The final assessment will consist of an extended essay on a topic agreed upon with the instructor in advance. • Identify materials for the creation and the transformation of concepts in multiple and non-synthetic dimensions. Explore The differences between the creation of art, fiction and the invention of philosophy and their potential commons as integrative objects. The commons are not defined by example but simply marked with the generic "X" which can exist within any form of knowledge and is the foundation of the future's mark within our present space.

Course

• Consider this exercise an extension of the line based diagram into three dimensional space, allot the object to be like a machine performing conceptual and literal functions. The transmutation of thought through the body into a new formation beyond the paper and the pen.

• Begin Preparation and discussion of collective and individual experiments via the matrix as demonstrated in Anne-Françoise Schmid's sample document.

• Present your findings to the class in week 3.

Texts:

• Interdisciplinarity on land and sea, philosophic fantasy Here students pair up and create appendages, modifications or correspondences with/for their comrades work.

The creation of an object or a philo-fiction and collective discussion on possibilities of a generic virtual space which create instances of their creative conjugation and disciplinary mutation will take place.

Texts:

• • Students as asked to set each other challenges to complete for the final session which will take the form of an exhibition of the future in a the virtual space of the classroom.

Texts:

• Exercise 5 : The Final Beginning

• Students present their respective projects from the course in the virtual exhibition space of the classroom .

• Students discuss how this ending is in fact a beginning.

• Platforms and potential manifestations of future collaborations are discussed.

Texts:

• Student Text

Explain our collaboration:

The Instructors have previously worked with each other to arrive at the concepts presented in this seminar. Anne-Francoise Schmid and Alice Lucy Rekab have developed theoretical means for new solidarities between art and philosophy (Liverpool, 2018). Schmid and Tony Yanick have developed a dispersive negation in contemporary integrative objects, those that do not support synthesis, to invent by abduction new links between these objects and philosophies (Milwaukee 2017 andLisbon 2017). Joevenn Neo works on Schmid's principal concepts in philosophy of sciences and is translating her latest book (Philosophical Scripts). These four instructors will work together according to their skills, in order to respond and deepen the problems proposed by the students.

•

  ScheduleWeek One: September 15th Le Voyage de la Fiction A transit between Futures and Fictions ____________• The Principles of Future and Fiction ○ The future is both a time and a mode, its reports to time are indirect • What is the organization between --fictions?○ Philo-fiction ○ Art-fiction ○ Science-fiction (not the genre)Exercise 1 : Response the course text through a line:• identify a concept or an image in one of the course texts or in response to the first lecture, develop your own two dimensional diagram which explicates and expands that concept within your own field of study. • Present your work to the class in week 2. Texts: Essay on introduction the future in epistemology • futur_espace_ethique Presentation • Les philosophes et le futur Jean-Noël Missa et Laurence Perbal (dir.) Vrin -Annales de l'institut de philosophie de l'université de Bruxelles 288 pages -13,5 × 21,5 cm ISBN 978-2-7116-2434-8 -septembre 2012 • The Silence of the future , conference, to be published in Philosophical Scripts Week Two: September 22nd La philosophie en objet intégratif Integrative Objects, Invention, & Fiction ____________ • Point of exteriority --invention • Tool --philo-fiction with introduction of point of exteriority • Between invention + fiction (not exactly the same) • Invention possible to be in Philosophy but with philo-fiction we NEED point of ext. • Le futur comme mode ○ Future becomes a cut in the present of the philosophy Exercise 2: Response to the text through a three dimensional material of your choosing.

  Le silence du futur, glossaire • Gilles-Gaston Granger & Jean-Toussaint Desanti, La Philosophie silencieuse et le Silence de la philosophie dans La Pensée de l'espace? • Second Chapter on Philosophical Scripts on Pragmatism • The Philosopher The Doesn't Speak Week Four: October 13th La futur-philosophie The Future-Philosophy ____________ • Le futur sans scénarios • Introduire le futur en philosophie • Le futur comme opérateur • La futur-philosophie • Science Future is new hypothesis --cut in reasoning • Aesthetics --Speculation / Construction in present / Nostalgia (messianic) • Le dispersible ∆Futur • ∆Futur, ∆Yes & ∆No • Future is a point --link between discipline --to put into relationship with the disciplines Exercise 4 : The Second Mutation : Set Your Comrades Final Challenge • We begin by discussing individual and collective responses to practice based exercises from weeks 1-3 and potential changes are discussed, improvised responses to each others work is encouraged and students are challenged to imagine how these conjugated practices made manifest in the previous weeks experiment might be further developed.

The First Mutation : Mutate your comrades work with a medium of your choice.

	• In Philosophy it is philosophies that are talking not The philosophy
	• space between --Espace générique des philosophies
	• obscure cogito, open secret
	• changes of scale
	Exercise 3:
	• On Contemporary Objects
	Week Three: September 29th
	Le silence du futur
	The Silence of the Future
	____________

• in science what is talking is the discipline (dynamic Silence of Science)

Section of Laruelle's "Phenomena and Difference"

	Texts:
	• New design en philosophie (art..science..etc) •
	• Découplage ? Indépendance ?
	• Immersion d'aliens
	Texts:
	• design in philosophy (text)
	• On Models --Anne-Françoise
	Week Seven: November 3rd
	futur-mystique
	Mystic-fiction & the Future
	____________
	Dispersible No, • Abduction
	• Genericity and Time • Mystical + Musical Philosophy
	• Religions
	Texts:
	Week Five: October 20th
	Art and Philosophy: reoriented Solidarities • Laruelle Mysticism and Contemporary Philosophy
	New Solidarities • Variations Film (Yanick)
	____________ • Essay to introduce into philosophy the affect of color
	• The prayer of the Nomoli
	• Philo-fiction dans la temporalité des arts et/ou des sciences
	• --construct new solidarities between
	Texts: Week Eight: November 10th
	Une philosophie sans futur ?
	• New Solidarities (Liverpool 2018, Alice and Anne-Françoise) --with Film Without a Future?
	____________
	• Liberté du futur
	Week Six: October 27th • Futur sans philosophie ?
	Design en philosophie • --Link philosophy + future
	New design in philosophy • Accelerationnism, deceleration --line of separation or gathering ? (Felix Ravaisson)
	____________

Explain collaboration with the students:

We ask to the students to read and write a text between each session --we combine all the texts and it will be the text for november 10th --30 mins to discuss a text of a student

We also ask the students to respond to the weekly exercises that call on the students individual disciplinary knowledges to produce a practice based response to the theory presented. Invention is superposition of voices and these exercises seek to embody this .

Maybe then our "responses" should be organized in this way (invention & fictions) Pedagogical organization

Future is an operator to make invention in each discipline IF future is silent --if this is silent we know future as a mark on the present. The practice asks students to make their futural marks on the present through the medium of the virtual classroom.

Know future as a cut in the present and this cut is a condition for invention Future is not from time before and after, its to a mode (cut in the present)

We know the future by the affect on our present

We can develop a methodology in fiction in all the disciplines, in arts, sciences, and philosophy, etc.

Bibliography (matériel supplémentaire)

François Laruelle, Christo-fiction. The Ruins of Athens and Jerusalem , Robin Mackay trans., Columbia University Press, 2015. Anne-Françoise Schmid & Armand Hatchuel, "On generic Epistemology", Angelaki, Journal of the Theoretical Humanities , vol.19, n° 2, 2014, pp. 131-144.


Anjo Anjewierden

Lilia Efimova
email: lilia.efimova@telin.nl

Understanding weblog communities through digital traces: a framework, a tool and an example

: researchers look at patterns in digital traces that members leave to characterise the community they belong to. Relatively easy access to these traces and a growing number of methods and tools to collect and analyse them make such analysis increasingly attractive. However, a researcher is faced with the difficult task of choosing which digital artefacts and which relations between them should be taken into account, and how the findings should be interpreted to say something meaningful about the community based on the traces of its members. In this paper we present a framework that allows categorising digital traces of an online community along five dimensions (people, documents, terms, links and time) and then describe a tool that supports the analysis of community traces by combining several of them, illustrating the types of analysis possible using a dataset from a weblog community.

Introduction

Although research on online communities has a long-standing history, the technological infrastructure and social structures behind them evolve over time. In this respect communities supported by weblogs is a relatively recent phenomenon.

A weblog is "a frequently updated web-site consisting of dated entries arranged in reverse chronological order" [START_REF] Walker | Weblog. Routledge Encyclopedia of Narrative Theory[END_REF]. Weblogs are often perceived as a form of individualistic expression, providing a "personal protected space" where a weblog author can communicate with others while retaining control [START_REF] Gumbrecht | Blogs as "protected space[END_REF]. On one hand, a randomly selected weblog shows limited interactivity and seldomly links to other weblogs [START_REF] Herring | Bridging the gap: A genre analysis of weblogs[END_REF]. On the other hand, there is growing evidence of social structures evolving around weblogs and their influence on norms and practices of blogging. This evidence ranges from voices of bloggers themselves speaking about the social effects of blogging, to studies on specific weblog communities with distinct cultures (e.g. [START_REF] Wei | Formation of norms in a blog community[END_REF]), to mathematical analysis of links between weblogs indicating that community formation in the blogosphere is not a random process, but an indication of shared interests binding bloggers together [START_REF] Kumand | Structure and evolution of blogspace[END_REF].

Often research on online communities could be compared to archaeology [START_REF] Jones | Virtual communities, virtual settlements, and cyber archaeolgy: a theoretical outline[END_REF]: researchers look at patterns in digital traces that members leave to characterise the community they belong to. In the case of weblog communities relatively easy access to these traces and a growing number of methods and tools to collect and analyse them make such analysis increasingly attractive (e.g. papers from the annual workshops on the Weblogging ecosystem at the WWW conference in 2004-06).

Many of the existing tools apply text or temporal analysis to large volumes of weblog data, often focusing on short bursts in time or popular topics (e.g. [START_REF] Adar | Implicit structure and the dynamics of blogspace[END_REF], [START_REF] Hurst | 24 hours in the blogosphere[END_REF], [START_REF] Thelwall | Blogs during the London attacks: Top information sources and topics[END_REF]). Others apply methods of social network analysis to identify and characterise networks between bloggers based on links between weblogs (e.g. [START_REF] Herring | Conversations in the blogosphere: An analysis "from the bottom-up[END_REF], [START_REF] Marlow | Investment and attention in the weblog community[END_REF]). In our work we focus on combining both in order to go beyond currently available views on weblog data, aiming at developing tools that take into account existing community structures [START_REF] Hodder | Link love lost or how social gestures within topic groups are more interesting than link counts[END_REF] and support the understanding of specific conversational clouds [START_REF] Levin | Conversation clouds[END_REF] and the "cloudmakers" behind them [START_REF] Ratcliff | Cloudmakers r us[END_REF]. Although our work is based on the analysis of digital artefacts that weblog community members leave online, we find it important to articulate explicitly how studying the results points to more general questions about weblog communities: which digital artefacts and which relations between them are taken into account, and how the findings should be interpreted to say something meaningful about the community based on the traces of its members.

In this paper we present a framework that allows categorization of digital traces of an online community along five dimensions (people, documents, terms, links and time) and then describe a tool that supports the analysis of community traces by combining several of these dimensions, illustrating the types of analysis possible using a dataset from a weblog community.

Framework

In this section we present a simple framework that can assist in the analysis of online communities. The formulation of the framework is motivated by the perceived need to provide community researchers with a conceptual tool to focus on particular aspects of the community.

There is a strong relation between the framework we propose and ongoing research into the study of online communities. The field of social network analysis (SNA) can be characterised by studying the relations between persons and their links, sometimes taking into account time. The field of text mining from communities, sometimes called semantic social network analysis [START_REF] Berendt | Finding your way through blogspace: using semantics for cross-domain blog analysis[END_REF], mainly looks at the relation between terms and documents, largely disregarding the notion of the individual. Finally, the area of identifying trends in communities (e.g. [START_REF] Gruhl | Information diffusion through blogspace[END_REF], [START_REF] Glance | WWW Workshop on the Weblogging Ecosystem: Aggregation, Analysis and Dynamics[END_REF]) looks at documents, terms and time. The research that is closest to what we are trying to achieve is work on iQuest by Gloor and Zhao [START_REF] Gloor | Analyzing actors and their discussion topics by semantic social network analysis[END_REF]. Their tool supports studying communities by making it possible to look at the community as a whole (topics discussed) and the contribution of members (who says what and when).

When thinking about online communities there are, therefore, at least five dimensions that play an important role and are possibly of interest for investigation: Document A self-contained publication by a member in the community. Examples of documents are a web page, email or weblog post. Term A meaningful term used by one or more members of the community. These terms occur in documents. Person A member of the community. Link A reference from one document to another document, and implicitly between the persons who authored the documents. Time The date, and possibly time, of publication of a document.

The framework thus focuses on communities that leave digital traces in the form of documents, and derives the other dimensions from the metadata (person, time) and content (terms, links). Given a dataset represented along these dimensions the researcher can navigate through it by specifying one or more initial dimensions, fixating a particular dimension (e.g. focusing on a particular term, person, or time period). Navigating along multiple dimensions makes it possible for the researcher to obtain both an overall view (what are the most frequent terms used in the community) and more detailed views (term usage of a particular member over time). The more dimensions involved, the more detailed, and maybe also the more interesting are the results of the analysis.

Tool

The framework has been implemented on top of a tool called tOKo [START_REF] Anjewierden | tOKo and Sigmund: text analysis support for ontology development and social research[END_REF]. tOKo is an open source tool for text analysis, with support for ontology development and, given the extensions described in this paper, exploring communities.

The only input tOKo requires is a corpus of (HTML) documents. Applied to community research, we assume a corpus represents the documents of the community under study. To be able to apply the framework it is necessary that for all documents the author (person) and the date of publication (time) is provided as metadata. Terms are automatically extracted by the Sigmund module of tOKo [START_REF] Anjewierden | Shared conceptualizations in weblogs[END_REF] which clusters lexical variants (abbreviations, inflections and alternate spellings) into a single, possibly compound, term. For example the term community has the lexical variants community and communities. Links between documents are by default extracted assuming the documents are HTML (anchor element). The implicit links between persons are inferred by considering the author of a document. After this extraction process is completed we have the data along all five dimensions for a given community represented by a corpus.

Fig. 1 shows the user interface of tOKo with the community research extensions. 3 The main difference between the base version of tOKo and the extension are additional methods and visualisations to cater for the links and time dimensions. The community research functions are available through the Community popup in the menubar and by clikcing inside the five browsers with community data at the top.

Examples

Our research focuses on a cluster of weblogs in areas of knowledge management and social software. This is a dense social network of weblog authors, and may be classified as a community, given the many bonds and interactions between participants (see [START_REF] Efimova | Finding "the life between buildings": An approach for defining a weblog community[END_REF] for a discussion). The goal in this research is to understand how knowledge develops in a weblog community and to develop tools to monitor those processes. Although knowledge flows in a community are difficult to grasp with automatic analysis we focus on inferring them from combined investigation of patterns in language use and linking patterns between community members.

In the rest of this section we provide an example how the framework can be applied to address questions emerging in our study. In the analysis the tool is used to analyse a corpus of 6329 documents (weblog posts), over a period of a single year (2004), written by 24 persons (bloggers).

A researcher who wants to study a community asks herself questions. Answering such questions requires several transformations. First, a question will be related to a particular slice of the complete dataset according to the framework and the selection of the appropriate subset, which may result in less than five dimensions, is necessary. Second, on the resulting subset, some method of computation has to be applied. The particular method of computation obviously depends on the question asked, and in general the scientific community offers a wide variety of choices here. Finally, the results of the computation must be presented to the researcher. This is also the order we use in answering the questions below: relation to the framework, methods used and visualisation of the results. This is a question that can be answered by considering a single dimension: terms. The rightmost browser in Fig. 1 shows the most frequent terms for the community at hand, low-content and high-frequency terms have been filtered out by Sigmund. A researcher might, based on this list conclude that this is a "knowledge management community". The more frequent terms blog and post are the result of the publication medium.

A simple example of restricting the dataset is to only look at the terms of a single person. Some examples of the most frequent terms for individual members of the community are: P1: community, technology, virtual community, role, process; P2: knowledge management, organization, information, blog, article; P3: company, community, blog, corporate, knowledge management.

Q: How are community topics related to each other?

One approach to answering such a question is to consider an operationalisation of "related to" as "occurring in the same document". This, first of all, requires two dimensions: document and term. And secondly, we need a statistical method to compute the relevance of what it means for two terms to be in the same document. For the latter we use the co-occurrence metric defined in [START_REF] Anjewierden | Detecting knowledge flows in weblogs[END_REF]:

Definition: Let n(B | A) (respectively n(B | ¬A)
) be the number of occurrences of the term B in documents that contain the term A (respectively do not contain the term A), and likewise let n( * | A) (respectively n( * | ¬A)) be the total number of terms in the documents that contain the term A (respectively do not contain the term A). Then the co-occurrence degree c(B | A) is defined as

c(B | A) = n(B | A)/n( * | A) n(B | ¬A)/n( * | ¬A) , 0 ≤ c(B | A) ≤ ∞
We say that B co-occurs with A to at least degree

k if c(B | A) ≥ k. Note that c(B | A) = 1 if B is
as frequent in documents containing as it is in documents not containing A, i.e. that term B and A seem to be unrelated.

Fig. 2 shows a graph of the co-occurrence network of the term "instant messaging" for the entire community. Edges between terms denote high co-occurrence (degree > 1.5). For example, "instant messaging" has a high co-occurrence with both "telephony" and "bandwidth". In addition, "telephony" and "bandwidth" themselves also have a high co-occurrence with each other.

The co-occurrence metric thus provides a device that enables finding related terms in the community. Obviously, the same method can be applied to a member of the community by fixating a single point on the person dimension.

Q: Do community topics change over time?

This question involves the dimensions term and time. And the obvious way to answer it might be to plot the frequency of a term over time, similarly to what BlogPulse [START_REF] Glance | WWW Workshop on the Weblogging Ecosystem: Aggregation, Analysis and Dynamics[END_REF] does. There are, however, technical, social and perhaps principle reasons for not (only) using plain frequency over time. The technical reason is that frequency of term usage in a particular (small) community generally results in an irregular sequence of spikes that makes it difficult to identify trends. Trending frequency for very large communities (e.g. the entire blogosphere as with BlogPulse) does not have this problem: when a large event occurs, within days a significant proportion of the blogosphere will mention it. A social reason is that, because we are studying a community, there is a significant difference when a term is resonated in the community, compared to when it is not.

The social issue is addressed by considering that a community can be defined in terms of who-links-to-who (along the person dimension), but that the real discussions in the community in all likelihood consists of the linked documents. Put another way, there is a principle reason to view the community not just as the collection of all documents produced by the community, but to also look at the cross-section of the documents that are linked. In order to investigate this we split the dataset in two sub-sets depending on whether a link exists within the community as follows:

D linked = d i ∈ D | link(d i , d j ), person(d i ) = person(d j )
That is, D linked is the set of all documents linked in the community excluding self-links. D unlinked is the difference between D and D linked .

The technical issue is addressed by using tf.idf (term frequency vs. inverse document frequency) rather than frequency and by computing tf.idf over a sliding time-window to identify trends. The formula we use for determining the relevance of a term i for a document j is one of the many variants of tf.idf :

weight(i, j) = (1 + log(tf i,j )) * log(N/df j )
where tf i,j is the frequency of term i in document j, df j the number of documents that contain term i and N the total number of documents.

The time-window can be defined by the researcher, the default is a period of two weeks which takes into account that discussions in the blogosphere have a lag that is measured in terms of days rather than hours (as compared to discussions over email). Fig. 3. Trend of "knowledge management" for all, linked and unlinked posts Fig. 3 shows an example of the trend of the term "knowledge management" used in the community. The x-axis represents time in days and the y-axis is the moving tf.idf average over a period of two weeks. The three lines represent the values for the community as a whole (blue), linked documents (D linked , green) and unlinked posts (D unlinked , red). A conclusion that might be drawn from this visualisation is that "knowledge management" is more specific for linked posts than it is for unlinked posts and that this is the case continously. Therefore, KM is one of the key terms of the community.

A graph for the term "Skype", drawn using the same method, is shown in Fig. 4. The pattern which emerges is very different than the graph of KM. Skype is used in bursts from time-totime (green peaks), then dies away (unlinked usage is above linked usage). According to the terminology used by Gruhl et al. [START_REF] Gruhl | Information diffusion through blogspace[END_REF], in this community KM is a chatter term, whereas Skype occurs in spikes. Gruhl et al. look at all documents in their community and make no difference between whether links exist between documents. This corresponds to the average trend in the graphs and it is interesting to observe that both KM and Skype would be chatter topics using Gruhl's approach, whereas the inclusion of the link dimension reveals that in our community the trend patterns are different between how KM and Skype are used in discussions. We address this question by looking at term usage, other answers might come from studying linking practices (SNA). Intuitively, we can define that a person is aligned with the community when she uses the same terms at the same rate compared to the community as a whole. Terms that are used more often by a person (compared to the community), might point to expertise or a certain passion for such terms (and the topics these terms point to). The method we use to find terms that significantly identify a person compared to the community is to compute for each term the following:

IDF (i) = log(N/df i ) sig(i, p j ) = average((1 + log(tf i,j )) * IDF (i)), d j ∈ D pj
where D pj is the set of documents by person p j . In other words, we use the inverse document frequency (IDF) of the entire community and compare it to the average term frequency of a particular person. The results can be visualised by a list of the values for all terms. Fig. 5 shows a visualisation as a "fingerprint", sometimes referred to as a Zeitgeist. In this kind of visualisation the font size of a term increases with significance.

Q: What conversations occur in the community?

We define a conversation in a community as a set of documents that are linked directly or indirectly: if d 1 links to d 2 and d 3 links to d 2 all three documents are part of a single conversation [START_REF] Efimova | Weblog conversations[END_REF]. Fig. 6 gives an example of the visualisation of such a conversation. Left to right is the time dimension, top to bottom are the persons involved in the conversation (in the tool the names are printed to the left of the boxes). The small coloured rectangles are the documents making up the A related question that could be asked is: what is this conversation about? For this we use the same technique as with fingerprinting, and for this conversation, it results in the following terms being the most significant (compared to all documents in the community): KM Europe, personal knowledge management [workshop], keynote, workshop, Amsterdam, etc. The conversation was about a personal knowledge management workshop at KM Europe in Amsterdam. The researcher can guess this from the above list of terms or by inspecting the documents making up the conversation in more detail.

The wavelike lines for each person shows the use of the term "personal knowledge management" over time (tf.idf for the given person). As can be observed the second person mentions this term regularly, whereas some of the other participants only pick it up when entering the conversation. Such visualisations can perhaps be used to identify when the community picks up a new term and study the stickiness of terms over time.

Finally, we note that Fig. 6 contains datapoints from all five dimensions from the framework in a two-dimensional visualisation.

Conclusions

In this paper we presented a framework that allows categorising digital traces of an online community along five dimensions (people, documents, terms, links and time) and illustrated how it can be applied to translate general questions about a weblog community and its members into specific questions that could be answered with specific sub-sets of the data and specific methods for analysis.

In addition to supporting research on communities the approach we propose might be useful for community members, facilitators or sponsors. For example, newcomers are often overwhelmed by a wealth of information available in a community and find it difficult to navigate between multiple digital artefacts or find the right people to address. Dimensions of our framework could provide an additional way to navigate those, for example, by discovering documents or people associated with their own topic of interest. Community moderators or sponsors might be interested in identifying trends over time, to monitor patterns of activity (e.g. dynamics conversations) or to identify emergent "hot" topics or thought-leaders in order to adjust necessary support.

We find the framework and its implementation useful in several respects. First, it supports translating research questions into questions that could be answered based on a definite number of dimensions directly connected to the data available from the community interactions. Second, it inspires thinking of alternative ways to answer research questions by looking at combinations of the dimensions of data which might otherwise be missed. Third, it allows us to quickly compare alternate methods or research questions proposed in the literature. Finally, although our examples in this paper refer to a weblog community, our experience elsewhere suggests that the framework could be useful in other online community cases, for example for analysing forum-supported communities such as communities of practice.

Apart from extending the tool and its functionality we see two major challenges going forward. The main challenge is that we desperately need an "automatic" method to derive topics. Some researchers avoid this issue by simply stating term equals topic. Others are seriously addressing the topic issue, but report that automatically extracting them from weblog data is nontrivial [START_REF] Berendt | Finding your way through blogspace: using semantics for cross-domain blog analysis[END_REF]. Another challenge is to provide a user interface that allows a researcher to enter a question directly. Currently, the user interface is extended with a new control for each type of question.

Fig. 1 .

 1 Fig. 1. Screenshot of the tOKo user interface with community research extensions

Fig. 2 .

 2 Fig. 2. Network of terms that have a high co-occurrence with "instant messaging" in the community

Fig. 4 .

 4 Fig. 4. Trend of "Skype" for all, linked and unlinked posts

Fig. 5 .

 5 Fig. 5. "Fingerprint" of term usage a person with respect to the community

Fig. 6 .

 6 Fig. 6. An example of visualising a conversation

  Anjewierden, A. & Efimova, L. (2006). Understanding weblog communities through digital traces: a framework, a tool and an example, International Workshop on Community Informatics (COMINF 2006), Montpellier, 2006 (November). In: On the Move to Meaningful Internet Systems 2006, Robert Meersman, Zahir Tari and Pilar Herrero et al. (eds.), pp. 279-289, LNCS 4277, Springer. This is the author's version of the article published in Lecture Notes in Computer Science © Springer, 2006. The original publication is available at http://www.springerlink.com/content/yv8426777458144x/

All other figures in this paper just show the content of the Graph sub-window.

http://metis.telin.nl

Acknowledgements. The authors wish to thank Robert de Hoog and Rogier Brussee for their contributions to the underlying work and the reviewers for their constructive comments. This work was partly supported by the Metis project 4 . Metis is an initiative of the Telematica Instituut, Basell and Océ. Other partners are CeTIM, Technical University Delft, University of Amsterdam, University of Tilburg and University of Twente (all in The Netherlands).


Michael Schnell

Sophie Couffignal

Jean Lieber

Stéphanie Saleh

Nicolas Jay
email: n.jay@chru-nancy.fr

Interpretation of Best Medical Coding Practices by Case-Based Reasoning -A User Assistance Prototype for Data Collection for Cancer Registries

Keywords: interpretation of best practices, interpretive case-based reasoning, coding standards, cancer registries, user assistance, decision support

In the fight against cancer, cancer registries are an important tool. At the heart of these registries is the data collection and coding process. This process is ruled by complex international standards and numerous best practices, which can easily overwhelm (coding) operators. In this paper, a system assisting operators in the interpretation of best medical coding practices and a short evaluation are presented. By leveraging the arguments used by the coding experts to determine the best coding option, the proposed system answers coding questions from operators and provides a partial explanation for the proposed solution.

Introduction

There are numerous cancer registries around the world collecting data about cancers diagnosed and/or treated in a given area. This data is used to monitor cancer (incidence rates, survival rates, etc.) and to evaluate cancer care (diagnosis, treatment, etc.). To produce comparable data, common definitions (e.g. terminologies like the International Classification of Diseases (ICD)) and coding practices [START_REF] Tyczynski | Standards and guidelines for cancer registration in Europe: the ENCR recommendations[END_REF] have to be followed. However, the broadness and complexity of these standards make the work of the medical staff in charge of coding (operators) more difficult.

The aim of this research is to address this complexity, by assisting both operators and coding experts in the interpretation of coding best practices.

As an illustrating example, let us consider the case denoted by exmpl of a particular woman. In 2016, multiple pulmonary opacities were discovered within her right lung. A CT scan indicated no mediastinal adenopathy. 4 A histological analysis of a sample identified the morphology 5 of the cancer as adenocarcinoma. The TTF1 marker test was positive. After further testing, another tumor is found in the ovaries. An operator might wonder which topography6 should be coded (lung or ovaries?) and can request help. For the Luxembourg National Cancer Registry (NCR), operators ask their questions using an online ticketing system. With free text description provided by operators, coding experts provide a solution, i.e. an answer with their reasoning in the form of a motivated argument.

Section 2 describes an approach to assist the data collection process for cancer registries and how case-based reasoning (CBR [START_REF] Aamodt | Case-based reasoning: Foundational issues, methodological variations, and system approaches[END_REF]) is applied. In Section 3, a prototype and preliminary results are discussed. Section 4 presents a conclusion and points out what further efforts need to be undertaken in the future.

Case-based interpretation of best practices

This article summarizes the work presented in [START_REF] Schnell | Case-Based Interpretation of Best Medical Coding Practices -Application to Data Collection for Cancer Registries[END_REF] and adds a description of the developed prototype and some preliminary results.

Preliminaries

RDFS7 is a knowledge representation language of the semantic web. SPARQL 7 is a query language for RDFS web.

A case (srce, sol(srce)) is composed of two parts: (1) srce is a problem given by a question (i.e. a subject) and a patient record, and (2) sol(srce) a solution for the problem srce.

The question indicates the subject (incidence date, topography, tumor nature, etc.). In the example, the question is about the topography.

The patient record represents the data from the hospital patient record (patient features, tumors, exams, treatments, etc.) needed to answer the question. The relevant data depends on the subject and is defined by coding experts. The patient record is represented by an RDFS graph [START_REF] Brickley | RDF Schema 1.1[END_REF] (see figure 1). Body parts and cancer morphologies use classes from the SNOMED Clinical Terms8 ontology.

The solution contains the answer to the question and the most important arguments in favor of (pros) and against (cons) this answer. In the example, the answer is to consider the topography to be the ovaries. The presence of multiple pulmonary opacities is an argument in favor, as they are indicative of a lung metastasis and thus the tumor is unlikely to have originated in the lungs.

The arguments have two uses. They help explain the answer to operators and serve as a reminder for coding experts. They are also used in the proposed approach during the retrieval step. Three types of arguments will be considered: strong pros, weak pros and weak cons. The difference between a strong and a weak argument comes from their reliability for a given conclusion. A strong argument is considered to be a sufficient justification for an answer, unlike a weak argument which is more of an indication or clue. It can be noted that there are no strong cons in the source cases. Indeed, such an argument would be an absolute argument against the given answer. Formally, an argument is a function that associates a Boolean to a case and is stored as a SPARQL ASK query. The following shows an argument arg, followed by an explanation: ?finding present yes . } arg says that a TTF1 positive adenocarcinoma is in favor of a primitive lung cancer. The argument checks that the morphology of the tumor is of type adeno-carcinoma and that the tumor is positive for the TTF1 marker. This argument applies for the example described in the introduction, i.e. arg(exmpl) = TRUE.

arg(case) = ASK {

Global architecture

The proposed approach uses a 4-R cycle (retrieve, reuse, revise, retain) adapted from [START_REF] Aamodt | Case-based reasoning: Foundational issues, methodological variations, and system approaches[END_REF] and four knowledge containers [START_REF] Richter | Case-based reasoning: a textbook[END_REF] (case base, domain knowledge, retrieval knowledge, adaptation knowledge), as shown in figure 2.

Retrieve

The proposed approach relies on arguments to find similar cases. Indeed, similar answers should be based on similar reasoning and thus the same arguments should apply. Our method checks the applicability of arguments from source cases on the target problem tgt and uses this to determine the preferred source case to solve tgt. This preference relation is denoted by the preorder tgt . The comparison between two source cases i and j relies on three criteria, C s for strong arguments, C w for weak arguments and C dist for patient records. An argument arg is applicable for a case c if the preconditions of the argument are met in the patient record of c. For the argument arg described in the preliminaries, arg applies for a case if the patient record contains at least two exams, one identifying the morphology as adenocarcinoma and another exam reporting a TTF1 positive tumor. Formally an argument arg is applicable for a case c if arg(c) = TRUE.

For the criterion C s , the source case with more applicable strong arguments is preferred. Formally, C s is met if ∆ s i,j > 0, where ∆ s i,j is defined as

∆ s i,j = N sp (srce i , tgt) -N sp (srce j , tgt)
and N args (srce, tgt) denotes the number of arguments of type args of a the source case srce which are applicable for a case tgt, i.e.

N args (srce, tgt) = |{a ∈ args(srce) | a(tgt) = TRUE}| and args ∈ {sp, wp, wc} is an argument type. sp(srce) is the set of strong pros, wp(srce) the set of weak pros and wc(srce) the set of weak cons of srce.

For the criterion for weak arguments C w , a combination of pros and cons is used. Intuitively, if more weak pros and less weak cons are applicable, the source case is preferred. Formally, C w is met if ∆ w i,j > 0, where ∆ w i,j is defined as

∆ w i,j = λ p * (N wp (srce i , tgt) -N wp (srce j , tgt)) -λ c * (N wc (srce i , tgt) -N wc (srce j , tgt))
where λ p and λ c are two nonnegative coefficients that are currently fixed to λ p = 3 and λ c = 2. When more data are available, these parameters values will be reevaluated.

For the criterion C dist , a graph edit distance between patient record RDFS graphs is used [START_REF] Bunke | Similarity measures for structured representations[END_REF]. Formally, C dist is met if ∆ dist i,j ≥ 0, where ∆ dist i,j is defined as

∆ dist i,j = dist(srce j , tgt) -dist(srce i , tgt)
The three criteria are considered lexicographically, first C s , then C w and finally C dist (see [START_REF] Schnell | Case-Based Interpretation of Best Medical Coding Practices -Application to Data Collection for Cancer Registries[END_REF]). srce i is preferred over srce 2 , i.e srce i tgt srce j , ifq ∆ s i,j > 0 or (∆ s i,j = 0 and (∆ w i,j > 0 or (∆ w i,j = 0 and ∆ dist i,j ≥ 0)))

Reuse

Once an appropriate source case has been found, the solution associated to the source case is copied: sol(tgt) := sol(srce). The arguments that do not apply to the target problem, if any, are removed.

Revise and retain

The newly formed case (tgt, sol(tgt)) can be reviewed by a coding expert, to modify the answer, the arguments and/or the patient record. A coding expert may choose to remove unnecessary information from the patient record, removing unwanted specificity. Thus, (tgt, sol(tgt)) is substituted by (tgt , sol(tgt )), where tgt is more general than tgt. (tgt , sol(tgt )) is a generalized case that has a larger coverage than (tgt, sol(tgt)) [START_REF] Maximini | An investigation of generalized cases[END_REF].

Prototype and preliminary results

The prototype designed for the NCR serves as a ticketing system, where operators ask coding questions and experts provide answers. It assists operators in structuring questions, making it easier for the NCR and coding experts to find similar questions later. For topography questions, it will also provide a tentative answer. This answer is calculated using the approach described in [START_REF] Schnell | Case-Based Interpretation of Best Medical Coding Practices -Application to Data Collection for Cancer Registries[END_REF]. All the answers are reviewed by experts. The prototype presents itself as a single page application built using Angular9 with a backing REST API built with Go 9 and the Gin framework. 10 The data is stored in a triple store Apache Jena and exposed as a SPARQL endpoint using Apache Fuseki.11 Figure 3 and4 show screenshots of the prototype. The prototype was tested internally, to perform a first assessment of its usability and utility. Some old cases concerning the topography were formalized and coded, with some domain knowledge. For the arguments, great care was given during modeling in order to make them more broadly applicable. Then new questions were presented to the system, and the proposed solution compared with the expected ones. While the prototype answered every question, not all of them were correct. The main reasons for the difference were the small amount of cases (15 originally, however the case base will be enriched by routine usage) and the simple reuse method used at this stage. Indeed, as the arguments have been formalized to be more general, some of the provided answers might be slightly incorrect (e.g. answering upper lung lobe instead of lower lung lobe). Despite this, as the prototype displays the reused source case, an operator should be able to make the necessary adaptation to the provided solution. For the questions concerning other subjects, the prototype relies entirely on the coding experts to provide answers.

To the best of our knowledge, few other reseach attempts to use arguments in the context of the retrieval process. The closest method found is a work by McSherry [START_REF] Mcsherry | Explaining the Pros and Cons of Conclusions in CBR[END_REF]. The proposed approach creates explanations afterwards, using the closest source case to provide the conclusion and the closest source case with the opposite conclusion to compute which attributes favor the conclusion and which attributes do not. Unlike our approach, each argument is linked to a single attribute. Thus they cannot show how the combination of attributes might influence a given outcome.

Recently there has been a growing interest for case-based reasoning applications in health sciences [START_REF] Bichindaritz | Case-based Reasoning in the Health Sciences[END_REF]. In this paper, an approach to assist operators in the interpretation of best medical coding practices has been proposed. This approach is based on discussions with operators and coding experts on actual coding problems. A dozen tricky problems were discussed in detail, among a hundred simpler problems. The coding questions asked by the operators are compared to previous questions and solved by reusing the pros and cons of previously given solutions. The results discussed are only preliminary and a more thorough evaluation, including the operators and coding experts, is planned.

At the moment the reasoning process is only partial. Arguments are only a part of a more complex reasoning process. The formalization of this process and the eventual integration of the coding standards remains an interesting avenue for future work.

After the prototype has been validated and improved by routine usage, a second version will be designed that is less domain-dependent. The objective is to build a generic system for argumentative case-based reasoning using semantic web standards.

Fig. 1 .

 1 Fig.1. Short patient record in RDFS. This graph represents a woman with a single biopsy (exam), identifying the tumor as adenocarcinoma (which is coded as M-8140/3). The circles represent blank nodes.

Fig. 2 .

 2 Fig. 2. Adapted 4-R cycle and knowledge containers for the proposed approach.

Fig. 3 .

 3 Fig. 3. Example of a solved case. The top displays the new question asked and the provided solution. The bottom displays the source case used to solve the new question.

Fig. 4 .

 4 Fig. 4. Form used to describe coding questions and patient records. The French labels for body parts and morphologies are taken from the SNMIFRE (a French translation of SNOMED, http://bioportal.lirmm.fr/ontologies/SNMIFRE).

An adenopathy is an enlargement of lymph nodes, likely due to cancer.

The morphology describes the type and behavior of the cells that compose the tumor.

The topography is the location where the tumor originated.

https://www.w3.org/TR/rdf-schema/ and https://www.w3.org/TR/sparql11-query

https://bioportal.bioontology.org/ontologies/SNOMEDCT

https://angular.io

https://golang.org, https://github.com/gin-gonic/gin

https://jena.apache.org/ and https://jena.apache.org/documentation/fuseki2/

Acknowledgments. The authors wish to thank the anonymous reviewers of the Joint Workshop on Artificial Intelligence in Health for their remarks which have helped in improving the quality of the paper. The first author would also like to thank the Fondation Cancer for their financial support.