Sylvain Gravier

Kahina Meslem

Simon Schmidt

Souad Slimani

A New Game Invariant of Graphs: the Game Distinguishing Number

Keywords: distinguishing number, graph automorphism, combinatorial game, hypercube

The distinguishing number of a graph G is a symmetry related graph invariant whose study started two decades ago. The distinguishing number D(G) is the least integer d such that G has a d-distinguishing coloring. A ddistinguishing coloring is a coloring c : V (G) → {1, ..., d} invariant only under the trivial automorphism. In this paper, we introduce a game variant of the distinguishing number. The distinguishing game is a game with two players, the Gentle and the Rascal, with antagonist goals. This game is played on a graph G with a set of d ∈ N * colors. Alternately, the two players choose a vertex of G and color it with one of the d colors. The game ends when all the vertices have been colored. Then the Gentle wins if the coloring is d-distinguishing and the Rascal wins otherwise. This game leads to define two new invariants for a graph G, which are the minimum numbers of colors needed to ensure that the Gentle has a winning strategy, depending on who starts. These invariants could be infinite, thus we start by giving sufficient conditions to have infinite distinguishing numbers, we also show that for graphs with cyclic automorphisms group of prime odd order, both game invariants are finite. After that, we define a class of graphs, the involutive graphs, for which the game distinguishing number can be quadratically bounded above by the classical distinguishing number. The definition of this class is closely related to imprimitive action whose blocks have size 2. Then, we apply results on involutive graphs to compute the exact value of these invariants for hypercubes and even cycles. Finally, we study odd cycles, for which we are able to compute the exact value when their order is not prime. In the prime order case, we give an upper bound of 3.

Background and definition of the game

The distinguishing number of a graph G is a symmetry related graph invariant. Its study started two decades ago in a work by Albertson and Collins [START_REF] Albertson | Symmetry breaking in graphs[END_REF]. Given a graph G the distinguishing number D(G) is the least integer d such that G has a d-distinguishing coloring. A d-distinguishing coloring is a coloring c : V (G) → {1, ..., d} invariant only under the trivial automorphism. More generally, we say that an automorphism σ of a graph G preserves the coloring c or is a colors preserving automorphism, if for all u ∈ V (G), c(u) = c(σ(u)). We denote by Aut(G), the automorphisms group of G. Clearly, for each coloring c of the vertex set of G, the set Aut c (G) = {σ ∈ Aut(G) : c • σ = c} is a subgroup of Aut(G). A coloring c is distinguishing if Aut c (G) is trivial. The group Aut(G) acts naturally on the set of its vertices and this action induces a partition of the vertex set V (G) into orbits. If H is a subgroup of Aut c (G) then the action of H on V (G) is such that each orbit induced by this action is monochromatic.

ISSN subm. to DMTCS c by the authors by the author(s) Distributed under a Creative Commons Attribution 4.0 International License In particular, an automorphism σ preserves the coloring if and only if the orbits under the action of the subgroup < σ > induced by σ, are all monochromatic.

In the last couple of years the study of this invariant was particularly flourishing. See [START_REF] Imrich | The distinguishing number of cartesian products of complete graphs[END_REF][START_REF] Imrich | Distinguishing cartesian powers of graphs[END_REF] for the work of Imrich, Jerebic and Klavžar on the distinguishing number of cartesian products or [START_REF] Collins | The Distinguishing chromatic number[END_REF] for an analog of Brook's theorem. Some variant of the distinguishing number have been already introduced. In [START_REF] Chan | The maximum distinguishing number of a group[END_REF][START_REF] Klavžar | Distinguishing labellings of group action on vector spaces and graphs[END_REF], an extension of the distinguishing number to any actions of a group H on a set X has been provided and in [START_REF] Collins | The Distinguishing chromatic number[END_REF] Collins and Trenk study a distinguishing coloring which must be also a proper coloring. Our goal in this paper is to introduce a game variant of this invariant in the spirit of the game chromatic number χ G introduced by Brahms in 1981 (see [START_REF] Faigle | On the game chromatic number of some classes of graphs[END_REF]) or of the most recent domination game (see [START_REF] Brešar | Domination game and an imagination strategy[END_REF]). Even if inventing new game invariant could raise up a lot of promising and interesting questions, it might seem artificial at a first glance. To defend our approach, we recall that game invariants have already proved useful to give a new insight on the classical invariant they are related to. We cite in particular [START_REF] Klavžar | Improved upper bounds on the domination number of graphs with minimum degree at least five[END_REF], where a greedy like strategy used in the study of the domination game is used to improve several upper bounds on the domination number. See also [START_REF] Kierstead | Efficient graph packing via game coloring[END_REF] for an application of coloring game to the graph packing problem.

The distinguishing game is a game with two players, the Gentle and the Rascal, with antagonist goals. This game is played on a graph G with a set of d ∈ N * colors. Alternately, the two players choose a vertex of G and color it with one of the d colors. The game ends when all the vertices have been colored. Then the Gentle wins if the coloring is d-distinguishing and the Rascal wins otherwise.

This game leads to two new invariants for a graph G. The G-game distinguishing number D G (G) is the minimum of colors needed to ensure that the Gentle has a winning strategy for the game on G, assuming he is playing first. If the Rascal is sure to win whatever the number of colors we allow, then D G (G) = ∞. Similarly, the R-game distinguishing number D R (G) is the minimum number of colors needed to ensure that the Gentle has a winning strategy, assuming the Rascal is playing first.

It arises directly from the definition that for any graph

G, D(G) ≤ D G (G) and D(G) ≤ D R (G).
Another straight forward remark is that the game distinguishing number of a graph and its complement are equal.

One natural question we start with is to know if having a winning strategy with k colors is a growing property. In other words, has the Gentle a winning strategy if k ≥ D G or k ≥ D R colors are allowed ? The answer is not as obvious as it looks at a first glance. We recall that for the game chromatic number χ g , it is not known if there is always a winning strategy if we play with k ≥ χ g colors. However for the game distinguishing numbers we easily show they both have this growing property. Proposition 1.1 Let G be a graph and k a positive integer. If k ≥ D G (G) (resp. k ≥ D R (G)), then the Gentle has a winning strategy with k colors, if he starts (resp. the Rascal starts).

Proof: In order to win with k colors, the Gentle plays the same winning strategy he would have played with D G (G) (resp. D R (G)) colors), except when the Rascal chooses a color strictly greater than D G (G) (resp. D R (G)). In that case, the Gentle plays the winning move, he would have played if the Rascal had played the colors 1. Let c be the final coloring in the game with k colors with respect to the above strategy. Let c be the coloring defined as follows:

∀v ∈ V (G) c(v) = c(v) if c(v) ≤ D G (G) (resp. c(v) ≤ D R (G)) 1 otherwise .
The coloring c is a distinguishing coloring since it is obtained by following a winning strategy for the game with only D G (G) (resp. D R (G)) colors. Let σ be an automorphism which preserves c. It is clear that σ preserves c too. Since c is distinguishing, σ must be the identity. This shows that c is a k-distinguishing coloring and that the Gentle has a winning strategy with k colors.

2 As mentioned in the definition D G and D R could be eventually infinite. For example, if the graph has an automorphism of order two, the Rascal can win using a strategy closed to the Tweedledee Tweedledum one for the sum of opposite combinatorial games. He uses the involutive automorphism to copy the move the Gentle just made. Proposition 1.2 If G is a graph with a non trivial automorphism of order 2, then:

1. D G (G) = ∞ if |V (G)| is even and 2. D R (G) = ∞, if |V (G)| is odd.
Proof: Let A be the set of vertices fixed by σ: A = {v ∈ G : σ(v) = v}. Note that |V (G)| and |A| have the same parity. We denote by r i and s i the i-th vertex played by the Rascal and the Gentle respectively.

First, assume |A| is even and the Gentle starts. The winning strategy for the Rascal is as follows. If s i is in A, then the Rascal plays another vertex r i in A and does not pay attention to the color. This is always possible since |A| is even. Else the Rascal plays such that r i = σ(s i ) and c(r i ) = c(s i ). Since σ has order 2, the vertices outside A can be grouped by pair (u, v) with σ(u) = v and σ(v) = u. Moreover the Gentle will be the first to play outside A. Hence such a move is always available for the Rascal. Now suppose |A| is odd and the Rascal begins. His first move is to color a vertex in A. The number of uncolored vertices in A are now even and it is the Gentle's turn. Then the Rascal wins with exactly the same strategy as above.

2 For example, for cycles C n or paths P n on n vertices, we have

D G (C n ) = D G (P n ) = ∞, if n is even, and D R (C n ) = D R (P n ) = ∞, if n is odd.
Note that proposition 1.2 tells nothing about the possible values of D G (resp. D R ) when the number of fixed points is odd (resp. even). For cycles the question is rather complicated. We partially solve it in section 4. But for paths P n , with n ≥ 2, it is easy to show that D G (P n ) = 2 (resp. D R (P n ) = 2) if n is odd (resp. even).

There are also graphs with both D G and D R infinite, for example graphs with two transpositions moving a common vertex, like the complete graphs on more than 3 vertices. Finding graphs with both invariants finite, is a bit less obvious. Before stating the result, we recall that for a given finite group Γ , there are infinitely many non-isomorphic graphs whose automorphism group is Γ .

Proposition 1.3 If G is a graph such that Aut(G) = Z/pZ, where p is prime and p ≥ 3, then D G (G) = D R (G) = 2.
Proof: Since |Aut(G)| is prime all the orbits under the action of the whole group have either cardinal 1 or cardinal p. Let O 1 , ...,O l , with l > 0 be the orbits of cardinal p. Since there is at least three distinct vertices in each orbit O i and two colored are allowed, the Gentle can always play, whoever starts, in a manner which ensures that at least one of the O i is not monochromatic.

Let σ be a non trivial automorphism of Aut(G). Since |Aut(G)| is prime, σ generates Aut(G) and the orbit under Aut(G) and < σ > are the same. The automorphism σ cannot preserve the coloring because in that case all the orbits O i have to be monochromatic. This shows that the above strategy is winning for the Gentle and that

D G (G) = D R (G) = 2.
2 Determining if D R or D G is finite is far from being easy in general. However, in the second section of this article, we introduce the class of involutive graphs, for which we prove that the R-game distinguishing number is finite and more precisely, quadratically bounded above by the classical distinguishing number of the graph. This class, closely related to imprimitive action of group with complete block system of size 2, contains a variety of graphs such as hypercubes, even cycles, spherical graphs and even graphs [START_REF] Koole | The structure of spherical graphs[END_REF][START_REF] Göbel | Even graphs[END_REF]. Then, in section 3, we specie the general result on involutive graphs to compute the exact values of the game invariants for hypercubes.

Theorem 1.4 Let Q n be the hypercube of dimension n ≥ 2.

1. We have D G (Q n ) = ∞. 2. If n ≥ 5, then D R (Q n ) = 2. Moreover D R (Q 2 ) = D R (Q 3 ) = 3. 3. We have 2 ≤ D R (Q 4 ) ≤ 3.
Finally, in section 4, we solve the problem for cycles, except when the number of vertices is prime. For even cycles, it is a straightforward application of a result on involutive graphs, but for odd cycles new ideas are needed.

Theorem 1.5 Let C n be a cycle of order n ≥ 3.

1. If n is even, then D G (C n ) = ∞. If n is odd, then D R (C n ) = ∞. 2. If n is even and n ≥ 8, then D R (C n ) = 2. Moreover D R (C 4 ) = D R (C 6 ) = 3. 3. If n is odd, not prime and n ≥ 9, then D G (C n ) = 2. 4. If n is prime and n ≥ 5, then D G (C n ) ≤ 3. Moreover D G (C 3 ) = ∞ and D G (C 5 ) = D G (C 7 ) = 3.

Involutive graphs

In this section, we introduce the new class of involutive graphs. This class contains well known graphs such as hypercubes, even cycles, even toroidal grids, spherical graphs and even graphs [START_REF] Koole | The structure of spherical graphs[END_REF][START_REF] Göbel | Even graphs[END_REF]. For graphs in this class, we are going to prove that their R-game distinguishing number is quadratically bounded above by the distinguishing number.

An involutive graph G is a graph together with an involution, bar : V (G) → V (G), which commutes with all automorphisms and have no fixed point. In others words:

• ∀u ∈ V (G) u = u and u = u, • ∀σ ∈ Aut(G) ∀u ∈ V (G) σ(u) = σ(u).
The set {u, u} will be called a block and ū will be called the opposite of u. An important remark is that, since bar commutes with all automorphism, the image of a block under an automorphism is also a block. The block terminology comes from imprimitive group action theory. Indeed, if we add the condition that the automorphism group of the graph acts transitively, then an involutive graph is a graph such that this action has a complete block system, whose blocks have size 2.

Before stating the results on involutive graphs, we want to emphasize that the no fixed point condition is not necessary but only convenient to write these results. With fixed points, we would have to permute who starts, depending on the parity of their number.

Let G be an involutive graph on n vertices. We define G as the graph obtained from G by deleting all the edges and putting a new edge between all vertices and their opposites. The resulting graph is a disjoint union of n/2 copies of K 2 . Moreover, it is also an involutive graph and it has the same blocks as G. The next proposition states that these graphs are in a sense the worst involutive graphs for the Gentle.

Proposition 2.1 If G is an involutive graph then D(G) ≤ D(G ) and D R (G) ≤ D R (G ).
Proof: It is enough to prove that any distinguishing coloring c of G is also a distinguishing coloring of G. Let σ be a non trivial automorphism of G. Assume first, there are two disjoint blocks {u, ū} and {v, v}, with u, v ∈ V (G), such that σ({u, ū}) = {v, v}. Since the coloring c is distinguishing for G , we have c({u, ū}) = c({v, v}). Hence, σ does not preserve c. Suppose now that there is not two such blocks. Since σ is not trivial, there exists u ∈ V (G) such that σ(u) = ū. But u and ū must have distinct colors, otherwise the transposition which switch them would be a non trivial colors preserving automorphism of G . Therefore, σ is not a colors preserving automorphism. We conclude that c is also a distinguishing coloring for G.

2 For graphs which are disjoint union of K 2 , we are able to compute the exact value of D G and D R .

Proposition 2.2 If G is the disjoint union of n ≥ 1 copies of K 2 , then D G (G) = ∞ and D R (G) = n + 1.
Proof: Such a graph G has an automorphism of order 2, with no fixed point, the one which exchanges the two vertices in each copy of K 2 . By Proposition 1.2, we directly conclude that D G (G) = ∞.

We are now going to prove that D R (G) = n + 1. First, assume that only k < n + 1 colors are allowed during the game. The Rascal's strategy is to play always the color 1 in a way that at least one vertex of each copy of K 2 is colored with 1. Since there is strictly less than n + 1 different colors, whatever the Gentle plays there will be two distinct K 2 colored with the same couple of colors or there will be a monochromatic K 2 . If there is a monochromatic K 2 , the transposition which permutes its two vertices is clearly a colors preserving automorphism. In the other case, there are four distinct vertices u 1 , u 2 , v 1 , v 2 ∈ V (G), such that u 1 and u 2 (resp. v 1 and v 2 ) are in the same K 2 . Moreover, u 1 and v 1 (resp. u 2 and v 2 ) share the same color. The automorphism σ, defined by σ(u

i ) = v i , σ(v i ) = u i , with i ∈ {1, 2}, and σ(w) = w for w ∈ V (G) \ {u 1 , u 2 , v 1 , v 2 }
preserves the coloring. Hence, the strategy described is winning for the Rascal. In conclusion, D R (G) ≥ n + 1.

We now allow n + 1 colors. We recall that the Rascal plays first. The winning strategy for the Gentle is as follows. He always colors the remaining uncolored vertex in the copy of K 2 , where the Rascal has just played before. He chooses his color such that the couple of colors for this K 2 is different from all the couples of colors of the previously totally colored copies of K 2 . Moreover, he ensures that no K 2 is monochromatic. This is possible because, even if the first color in a K 2 is fixed by the Rascal, the Gentle can make n different no monochromatic couples of colors. Let σ be a non trivial automorphism of G and let u ∈ V (G) be such that σ(u) = u. If u and σ(u) belong to the same copy of K 2 , σ does not preserve the coloring. Indeed, there is no monochromatic copy of K 2 . On the other hand, if u and σ(u) do not belong to the same copy, it means that the copy which contains u is sent by σ to the disjoint copy which contains σ(u). But each copy of K 2 has a unique couple of colors. Hence, σ is not a colors preserving automorphism. This shows that the Gentle has a winning strategy with n + 1 colors. In conclusion,

D R (G) = n + 1. 2 It is shown in [6], that if G consists in n ≥ 1 disjoint copies of K 2 , then D(G) = 1 + √ 8n + 1 2
. Hence, we get examples of graphs for which the R-game distinguishing number is quadratic in the classical one. The following results are straightforward application of Proposition 2.1 and Proposition 2.2. Proposition 2.3 If G is an involutive graph on n vertices, then:

• D(G) ≤ 1 + √ 4n + 1 2 and • D R (G) ≤ n 2 + 1.
This result shows that involutive graphs have finite R-game distinguishing number. But the bound we obtained does not depend on the classical distinguishing number of the graph. If the Gentle knows this number, having in mind a distinguishing coloring, he can use it to play in a smarter way. In other words, for an involutive graph G, we can bound the game distinguishing number D R using the classical one. It

turns out that D R (G) is in this case at most of order D(G) 2 . Theorem 2.4 If G is an involutive graph with D(G) ≥ 2, then D R (G) ≤ D(G) 2 + D(G) -2.
Proof: We set d = D(G). We are going to give a winning strategy for the Gentle with d 2 + d -2 colors. Note that, since the Rascal starts the game, the Gentle can play in a way he is never the first to color a vertex in a block. When the Rascal colors a vertex u ∈ V (G), the Gentle's strategy is to always answer by coloring the vertex u in same block.

Before stating how he chooses the color, we need some definitions. Let c be a distinguishing coloring of G with d ≥ 2 colors. We set k = d 2 + d -2. For all i, j ∈ {1, ..., d}, we define the following sets of vertices:

V ij = {u ∈ V (G)|c(u) = i and c(u) = j}. There are d(d-1)
2 sets V ij , with 1 ≤ i < j ≤ d, and d sets V ii , with i ∈ {1, ...d}. To each set V ij , with 1 ≤ i < j ≤ d, we associate a specific number δ ij in {1, ..., d(d-1) 2 }. For each V ij , with i, j ∈ {1, ...d}, we defined r ij as follows:

r ij =        δ ij if 1 ≤ i < j ≤ d k -r ji if 1 ≤ j < i ≤ d d(d-1) 2
+ i if i = j and 1 ≤ i ≤ d -1 0 if i = j = d
This defines only d 2 distinct numbers. We need despite d 2 + d -2 colors to ensure the second following properties:

• ( * ) ∀i, i , j, j ∈ {1, ..., d} r ij ≡ r i ,j [k] if and only if i = i and j = j , • ( * * ) ∀i, j ∈ {1, ..., d} if i = j, r ii ≡ -r jj [k].
Let now c : V (G) → {1, ..., k} be the coloring built during the game. The Gentle chooses the color as follows. When the Rascal colors

u ∈ V ij with c (u), he colors u such that c (u) -c (u) ≡ r ij [k].
To prove this strategy is winning, it is enough to show that for any automorphism σ which preserves c , we have σ(V ij ) = V ij . Since all V ij are monochromatic for the distinguishing coloring c, this will show that σ also preserves c and σ must therefore be the identity.

Let u be a vertex of G and i, j ∈ {1, ..., d}. We show that u ∈ V ij , with i = j, if and only if c (u

)-c (u) ≡ r ij [k] and u ∈ V ii if and only if c (u) -c (u) ≡ ±r ii [k]. First, assume that u ∈ V ij , with i = j. If u was colored by the Rascal, we have c (u) -c (u) ≡ r ij [k]. Else, u was colored by the Rascal. Since u is in V ji , we have c (u) -c (u) ≡ r ji ≡ -r ij [k]. Since r ij ≡ -r ji [k], we also conclude that c (u) -c (u) ≡ r ij [k]. Now, if u is in V ii , we only get that c (u) -c (u) ≡ ±r ii [k]. Reciprocally, assume that c (u) -c (u) ≡ ±r ij [k].
We have to prove that u belongs to V ij . The vertex u belongs to some set V lm , with l, m ∈ {1, ..., d}. By the previous part of the proof, we know that c (u

) -c (u) ≡ ±r lm [k]. Assume first that c (u) -c (u) ≡ r lm [k]
. By property ( * ), we conclude that i = l and j = m. In other words, u is in

V ij . Second, if c (u) -c (u) ≡ -r lm [k], we now that l = m. Hence, r ij ≡ -r ll [k]. It could happen only in two cases: i = j = l = d or i = j = l = d -1.
In both cases, it shows that u is in V ij . Finally, let σ be an automorphism which preserves c . For any vertex u ∈ V ij , with i, j ∈ {1, ..., d},

we have c (u) -c (u) ≡ c (σ(u)) -c (σ(u))[k]. Hence, c (σ(u)) -c (σ(u)) ≡ r ik [k]
and we conclude that σ(u) is in the same set V ij as u. 2 In the above proof, decreasing the number of sets V ij tightens the bound. In particular, we have the following corollary.

Corollary 2.5 Let G be an involutive graph. If there is a coloring with d ≥ 2 colors, such that bar is the only non trivial automorphism which preserves this coloring, then D R (G) ≤ 2d -2.

Proof: We use the same notations as in the proof of Theorem 2.4. As in this proof the Gentle uses the distinguishing coloring c with d colors to build his strategy. Since we ask that bar is preserved, all the set V ij , with i = j are empty. So the Gentle needs only 2d -2 colors to apply his strategy. Indeed, he plays in a way that for all

u ∈ V (G), c (ū) -c (u) ≡ i -1[2d -2]
, where i ∈ {1..., d} is such that u ∈ V ii . As for the proof of the previous theorem, we can prove that an automorphism which preserves the coloring c must also preserve the coloring c. Thus, it is either the identity or the bar involution. But, it is clear that the Gentle's strategy leads to at least one block which is not monochromatic. Hence the bar involution cannot preserve the coloring c . In conclusion, c is a distinguishing coloring and the Gentle has a winning strategy with 2d -2 colors. 2

Hypercubes

In this section, we use Corollary 2.5 to study the game distinguishing number of Q n , the hypercube of dimension n ≥ 2 and prove theorem 1.4. The vertices of Q n will be denoted by words of length n on the binary alphabet {0, 1}. For a vertex u, u(i) denotes its i-th letter. For the classical distinguishing number the question is solved in [START_REF] Bogstad | The distinguishing number of hypercubes[END_REF]:

D(Q 3 ) = D(Q 2 ) = 3 and D(Q n ) = 2 for n ≥ 4.
As mention before, hypercubes are involutive graphs. The bar involution can actually be defined as the application which switch all the letters 0 to 1 and all the letters 1 to 0. Moreover, this application is an automorphism. Hence, by Proposition 1.2, we know that

D G (Q n ) = ∞, for all n ≥ 2. If we apply directly Theorem 2.4, we obtain that D R (Q n ) ≤ 4, for n ≥ 2.
To improve this bound in order to prove the first item of Theorem 1.4, we are going to use Corollary 2.5. We will have to design nice distinguishing coloring of the hypercube with 2 colors. For this purpose, we introduce determining sets.

A subset S of vertices of a graph G is a determining set if the identity is the only automorphism of G whose restriction to S is the identity on S. Determining sets are introduced and studied in [START_REF] Boutin | Identifying graph automorphisms using determining sets[END_REF]. In the following lemma, we give a sufficient condition for a subset of Q n to be determining. Lemma 3.1 Let S be a subset of vertices of Q n , with n ≥ 2. If for all i ∈ {1, ..., n}, there are two vertices v i 0 and v i 1 such that v i 0 (i) = 0, v i 1 (i) = 1 and all the other letters are the same, then S is a determining set of Q n .

Proof: Let σ ∈ Aut(G), which is the identity on S. By absurd, suppose there exists a vertex u in Q n \ S such that σ(u) = u. Then, there exists k ∈ {1, ..., n} such that u(k) = σ(u)(k). Without lost of generality, we suppose that u(k) = 0. The vertices u and v k 0 differ on l letters, with l ∈ {1, ...n}. This means that the distance between u and v k 0 is equal to l. Since σ fixes v k 0 the distance between σ(u) and v k 0 must be l too. Therefore, the vertices u and v k 1 have l + 1 distinct letters, whereas the vertices σ(u) and v k

1 have only l -1 distinct letters. This is impossible because the distance between u and v k 1 must be the same as the distance between σ(u) and

v k 1 . Therefore σ(u) = u for all u ∈ V (Q n ). In conclusion S is a determining set. 2 Proposition 3.2 Let Q n be the n-dimensional hypercube with n ≥ 5. Then D R (Q n ) = 2.
Proof: For i ∈ {0, ..., n -1}, let v i be the vertex with the i first letters equal to 1 and the ni others letter equal to 0. We define also the following vertices in Q n : f = 10010...0, c 1 = 010...01 and c 2 = 110...01.

The subgraph S will be the graph induced by {v i , v i |0 ≤ i < n} ∪ {f, f , c 1 , c 1 , c 2 , c 2 } (see Fig. 1). Let c be the coloring with two colors defined by: c(u) = 1 if u ∈ V (S) and c(u) = 2 otherwise. We will show that this coloring fits hypothesis of Corollary 2.5. This would imply that

D R (Q n ) = 2 × 2 -2 = 2.
Clearly, bar is preserved and we prove now this is the only non trivial colors preserving automorphism. An automorphisms σ which preserves this coloring lets S stable: σ(S) = S. The restriction of σ to S, say σ| S , is an automorphism of S. The vertices v 0 , ...,v n-1 , and v 0 show that the subgraph S verifies Lemma 3.1 hypothesis. Hence σ is totally determined by the images of the elements of S. The two vertices f and f are the only vertices of degree 1 in S. So, either σ(f ) = f and σ(f ) = f or the both are fixed. In the first case, this implies that σ(v 1 ) = v 1 and σ(v 1 ) = v 1 . In the second case v 1 and v 1 are also fixed by σ. This is because they are respectively the only neighbors of f and f in S. The vertices v 0 and v 2 are the two remaining neighbors of v 1 . Since they have not the same degree in S, they can't be switched by σ. Hence, in the first case, σ(v i ) = v i and σ(v i ) = v i , with i ∈ {0, 2}. In the second case, v 0 and v 2 are fixed by σ. After that, it is easy to show that σ| S is either the identity or the bar involution. 2

The above proof fails for Q 4 because the subgraph S will have other automorphisms than the bar involution (see Fig. 2). We can despite decrease the upper bound from 4 to 3.

Proposition 3.3 We have D R (Q 4 ) ≤ 3.
Proof: Let S be the subgraph of Q 4 induced by the five vertices 0000, 1000, 1100, 1110 and 1011. Let S be the subgraphs induced by the opposite vertices of those in S. Note that S and S are disjoint. The Gentle's strategy is as follows. When the Rascal colors a vertex u in V (G), the Gentle colors u. He chooses the coloring c according to these rules:

• if u is in V (S), c(u) -c(u) ≡ 1[3], • if u is in V (S) c(u) -c(u) ≡ -1[3], • c(u) -c(u) ≡ 0[3] otherwise. v 0 v0 f f c 1 c1 c 2 c2 v 1 v 2 v 3 v 4 v1 v2 v3 v4 Figure 1: The induced subgraph S in Q 5 . v 0 v0 f f c 1 c1 c 2 c2 v 1 v 2 v 3 v1 v2 v3 Figure 2: The induced subgraph S in Q 4 . • if u is in V (S), c(u) -c(u) ≡ 1[3], • if u is in V (S) c(u) -c(u) ≡ -1[3], • c(u) -c(u) ≡ 0[3] otherwise.
Let σ be a colors preserving automorphism. Then S is stable under σ: σ(S) = S. Let σ| S be the restriction of σ to S. The vertices 0000 and 1110 are the only vertices of degree 1 in S.

v 0 v0 f f c 1 c1 c 2 c2 v 1 v 2 v 3 v 4 v1 v2 v3 v4 Figure 1: The induced subgraph S in Q 5 . v 0 v0 f f c 1 c1 c 2 c2 v 1 v 2 v 3 v1 v2 v3 Figure 2: The induced subgraph S in Q 4 . • if u is in V (S), c(u) -c(u) ≡ 1[3], • if u is in V (S) c(u) -c(u) ≡ -1[3], • c(u) -c(u) ≡ 0[3] otherwise.
Let σ be a colors preserving automorphism. Then S is stable under σ: σ(S) = S. Let σ| S be the restriction of σ to S. The vertices 0000 and 1110 are the only vertices of degree 1 in S. Let σ be a colors preserving automorphism. Then S is stable under σ: σ(S) = S. Let σ| S be the restriction of σ to S. The vertices 0000 and 1110 are the only vertices of degree 1 in S. Then either σ| S fixes them or switches them. But in Q 4 , we have d(0000, 1011) = d(1110, 1011). Since σ| S comes from an automorphism of Q n , it must preserve distances in Q n . But, the vertex 1011 is fixed by σ| S because it is the only isolated vertex of S. Hence, we have that σ| S fixed 0000 and 1110. After that, it is clear that all the vertices of S are fixed by σ| S and hence by σ. The vertex 1111 is also fixed by σ, because it is the opposite vertex of 0000. Finally, all the vertices of V (S) ∪ {1111} are fixed by σ and this subset fits hypothesis of Lemma 3.1. This shows that σ is the identity of Q 4 . 2 To complete the proof of Theorem 1.4, it remains to settle the case of hypercubes of dimension 2 and 3. For the square Q 2 , isomorphic to C 4 , an easy computation shows that D R (Q 2 ) = 3. For Q 3 , it turns out that D R (Q 3 ) is also equal to 3. It comes from the fact that the complementary graph of Q 3 is isomorphic to K 4 K 2 and from the following proposition.

We will write the vertices of K 4 K 2 as couples (i, x), with i ∈ {1, ..., 4} and x ∈ {l, r}. The first coordinate is the one associated to K 4 and the second the one associated to K 2 . We denote by K i 2 the K 2 -fiber whose two vertices have i ∈ {1, ..., 4} as first coordinate. Let c be a coloring of K 4 K 2 . We say that two distinct K 2 -fibers, K i 2 and K j 2 , with i, j ∈ {1, ..., 4} are colored the same if c(K i 2 ) = c(K j 2 ). Moreover, if c((i, l)) = c((j, l)), we say that the two fibers are strictly colored the same.

Proposition 3.4 We have D R (K 4 K 2 ) = 3.
Proof: Since D(K 4 K 2 ) = 3, we only have to prove that the Gentle has a winning strategy with 3 colors. The Rascal starts by coloring the vertex (1, l) with 1. The Gentle replies by coloring with 2 the vertex (2, l). Now, there is two cases.

Case 1: The Rascal colors the second vertex of K 1 2 or K 2 2 with the colors δ ∈ {1, 2, 3}. Without lost of generality we assume he colors (1, r). There is two sub cases. 1.1: δ ∈ {1, 3}. The Gentle colors (2, r) with 2. The Gentle's strategy is now to play in the same K 2 -fiber as Rascal. Since the two K 2 -fibers K 1 2 and K 2 2 share no color, the Gentle can ensure that at the end of the game no pair of K 2 -fibers are colored the same and K 3 2 is not monochromatic. This shows that a colors preserving automorphism σ cannot switch the K 2 -fibers. Hence σ(K 3 2 ) = K 3 2 and, since this fiber is not monochromatic, we have that σ cannot switch the K 4 -fibers too. Finally σ is the identity.

1.2: δ = 2. The Gentle colors (2, r) with the colors 1. By coloring the vertices in the same K 2 -fiber as the vertices the Rascal will play, the Gentle can ensure that at the end of the game K 3 2 is not monochromatic and is neither strictly colored the same as K 1 2 and K 2 2 nor as K 4 2 . Hence σ(K 3 2 ) = K 3 2 and K 3 2 is not monochromatic. This shows that σ cannot switch the K 4 -fibers. Moreover, he can also force that no pair of K 2 -fibers is strictly colored the same. But the two fibers K 1 2 and K 2 2 are colored the same. Let σ be a colors preserving automorphism. Since no pair of K 2 -fibers are strictly colored the same, the automorphism cannot permute the K 2 -fibers without switching the two K 4 -fibers. But the fiber K 3 2 forbids this case. Finally σ fixes the K 2 -fibers too and must therefore be the identity.

Case 2: The Rascal colors the vertex (3, x), with x ∈ {l, r}. The Gentle answers by coloring the vertex (4, x). The Gentle chooses his colors such that we can assume (1, l) and (3, x) are colored with 1, (2, l) is colored with 2 and (4, x) is colored with 3 (maybe we need to permute the name of the colors 1 and 2). We only deal with the case where x = l. The case where x = r is very similar. When the Rascal's move is to color (1, r) (resp. (3, r)), the Gentle answers by coloring (3, r) (resp. (1, r)). When the Rascal's move is to color (2, r) (resp. (4, r)), the Gentle answers by coloring (4, r) (resp. (2, r)). He can choose the colors he uses, such that no pair of K 2 -fibers is strictly colored the same. Moreover, one of the four K 2 -fibers is not monochromatic and is not colored the same as each of the three other K 2 -fibers. At the end of the game, we are in the same situation as in sub case 1.2. In conclusion, the coloring built in this case is also 3-distinguishing. 2

Cycles

In this section, we prove Theorem 1.5 about cycles. We start with even cycles which are involutive graphs. For such graphs, the opposite of a vertex can be defined as the unique vertex at maximal distance. Corollary 2.5 enables us to conclude when the size of the even cycle is greater or equal to 12. For the smaller cycles a brute force computation gives: This block is the axis of the symmetry. Since 2n ≥ 12, we easily check that the two other blocks cannot be map to each other by this symmetry. Since σ cannot be a symmetry, σ must be a rotation. The only possibility for a rotation to let S stable is to map each vertex to its opposite. Hence σ restricted to S is the bar involution. But, its straightforward to show that σ must be the bar involution on the whole cycle. This shows that the coloring c fits Corollary 2.5 hypothesis. We conclude that D R (C 2n ) ≤ 2. 2 We compute now the G-game distinguishing number for odd, but not prime cycles. Odd cycles are not involutive graphs, but when the number n of vertices is not prime, the action of the automorphism group is not primitive. We are going to use a complete block system, with blocks of size equal to the least prime divisor of n. For C 9 , the general strategy fails. By brute force computation, we get D G (C 9 ) = 2.

D R (C 4 ) = D R (C 6 ) = 3 and D R (C 8 ) = D R (C 10 ) = 2.
To shorten the proofs, we introduce the following technical lemma.

Lemma 4.2 Let G be a graph and V 1 ,V 2 and V 3 be a partition of V (G) such as:

|V 1 | = |V 2 |, |V 1 | ≥ 2
and |V 3 | is odd. We assume that the Gentle starts and plays as follows.

• The Gentle's first move is in V 3 .

• If the Rascal plays in V 3 , the Gentle answers by playing in V 3 too.

• If the Rascal plays in V 1 (resp. V 2 ), then he plays in V 2 (resp. V 1 ). Except if the Rascal colors the penultimate vertex of V 1 (resp. V 2 ). In this case, he colors the last vertex of V 1 (resp. V 2 ).
Then the above strategy is always possible and leads the Gentle to play the last vertex in V 1 and V 2 .

Proof: Do an induction on

|V 1 | + |V 3 |. 2 Proposition 4.3 If C n is an odd cycle such that n > 9 and n is not prime, then D G (C n ) = 2.
Proof: Let p be the least prime divisor of n. Since n ≥ 15, we have n = kp with k ≥ 5. Let (x 1 , ..., x n ) be the cycle C n . We defined k disjoint subsets of vertices V j = {x j+lk |l ∈ {0, ..., p -1}}, with j ∈ {1, ..., k}. The set V 1 will play a particular role. We denote by ∆ i , with i ∈ {1, ..., p}, the axial symmetry with fixed point x 1+(i-1)k . Note that an automorphisms ∆ i , with i ∈ {1, ..., p}, moves the sets V j , with j ∈ {1, ..., k}, in the following way:

∆ i (V 1 ) = V 1 and for j = 1, ∆ i (V j ) = V k+2-j . Since k is odd, j = k + 2 -j and ∆ i (V j ) = V j , if j = 1.
We describe the Gentle's strategy. He starts to color a vertex in V 1 with 1. More precisely, he chooses the fixed point of ∆ 1 .

• If the Rascal colors a vertex x in V 1 , he answers by coloring the vertex ∆ 1 (x) in V 1 with the other color. Note that since the Gentle starts the game by coloring the fixed point of ∆ 1 , this is always possible. Therefore, ∆ 1 is broken and there will be exactly 1 + p-1 2 vertices colored with 1 in V 1 at the end of the game.

• If the Rascal plays in V j , with j = 1, then he plays in V k+2-j . Except if the Rascal just colors the penultimate vertex of V j . In that case he plays in V j too, and colors the last vertex in a way the parity of the number of 1 in V j is not the same as the parity of 1 + p-1 2 . The vertex he chooses to color in V k+2-j is determined as follows. If at least one symmetry ∆ i , with i ∈ {2, ..., p}, is not already broken by the coloring, he chooses one of them, say ∆ i0 . We call V j the set of already colored vertices in V j . There is exactly one more colored vertex in V j , than in V k+2-j . Hence ∆ i0 (V j ) has at least an uncolored vertex, say u. The Gentle colors u such as u and ∆ -1 i0 (u) are not of the same color. If all the symmetries ∆ i are already broken, he plays randomly in V k+2-j .

At the end of the game, there are exactly 1 + p-1 2 vertices colored with 1 in V 1 . Thanks to Lemma 4.2, we see that the Gentle will be the last to play in each V j , with j = 1. So in all these V j , the number of 1 has not the same parity as in V 1 . This proves that the only possible colors preserving automorphisms are those under which V 1 is stable. The Gentle plays (k-1)p 2 moves outside V 1 . There are only k -1 moves used to control the parity of the 1. The number of remaining moves to break the p -1 symmetries ∆ 2 , ...,∆ p is (p-2)(k-1)

2

. Since k ≥ p and k ≥ 5, this number is greater or equal to p -1. This shows that all the symmetries under which V 1 is stable are broken. A colors preserving automorphism σ is finally either a rotation under which V 1 is stable or the identity. Assume σ is a rotation. The subgroup < σ > acts naturally on V 1 . But |V 1 | is prime, then < σ > must be of order p and acts transitively on V 1 . This is impossible because V 1 is not monochromatic. In conclusion, σ must be the identity and the Gentle has a winning strategy with two colors.

2 To finish the proof of Theorem 1.5, we deal with prime cycles. Note that, in that case, the automorphisms group action is primitive. Once more, the small case C 5 does not fit the general strategy. By computation, we get D G (C 5 ) = 3. Proof: Assume that three colors are allowed during the game. We begin the proof by showing the Rascal cannot win if he does not always play the same color as the one used by the Gentle just before. We denote respectively by n 1 , n 2 and n 3 , the number of vertices colored with 1, 2 and 3 during the game. As long as the Rascal copies the color played by the Gentle just before, the three numbers n 1 , n 2 and n 3 are even at the end of the Rascal's turn. The first time the Rascal plays a different color, two of the three numbers, n 1 , n 2 and n 3 are odd at the end of his turn. Without lost of generality, we can say n 1 and n 2 are odd. Then the Gentle colors a vertex with 3. The numbers n 1 , n 2 and n 3 are now all odd. Until the end of the game, the Gentle strategy is now to play the same color as the one the Rascal just used before him. In this way, he preserves the parity of n 1 , n 2 and n 3 . At the end of the game, the coloring is such as n 1 , n 2 and n 3 are odd. We show that this coloring is a distinguishing coloring. Let σ be a colors preserving automorphism. The cardinal of an orbit O under the action of < σ > must divide | < σ > |. But the cardinal | < σ > | is either 1, 2 or p. Then, this orbit has 1, 2 or p as cardinal. None of n 1 , n 2 and n 3 are null, so the coloring is not monochromatic and then the cardinal of O cannot be p. The automorphism σ cannot be a rotation because, for prime cycle, a rotation acts transitively and has an orbit of size p. Assume σ is a symmetry. Then, there is exactly one fixed point. Without lost of generality, we suppose it is colored 1. All the vertices colored with 2 are in orbits of size 2. Since n 2 is not null, there are k > 0 such orbits. We get n 2 = 2k, which is a contradiction. Hence σ must be the identity.

We can now assume that the Rascal always copies the color played by the Gentle just before. Playing another move will actually lead him to defeat, whatever has happened before. The winning strategy for the Gentle is as follows. He starts with a 1 and his second move is to color a vertex with a 2. The Rascal's second move must also be a 2. Let σ 2 be the symmetry which switches the two vertices colored with 2 and v the vertex fixed by σ 2 . If v is already colored, the Gentle plays a 1 wherever he wants. If not, he colors v with 1. After that, the Gentle always used the color 1, except for his last turn, where he will play a 3. Since p > 5, he really has enough turns to play this 3. At the end of the game, the coloring has the following properties: exactly two vertices are colored with 2 and exactly one vertex is colored with 3. Since there is only one vertex colored with 3 no rotation can preserve the coloring. Since there are only two vertices colored with 2, the only possible colors preserving symmetry is σ 2 . But the Gentle played in a manner that the unique 3 is not the fixed point of this symmetry. In conclusion, the coloring is distinguishing and the Gentle wins with 3 colors. 2

Conclusion and further works

In this article, we have defined two new game invariants of graphs, in the same spirit as the game chromatic number or as the game domination number. Since these invariants could be infinite, we started by giving some sufficient conditions for a graph to have infinite game distinguishing numbers. But a total characterization seems far to be found and sounds like a very challenging open problem. We propose the following conjecture. After that, we defined a new class of graphs, the involutive graphs, for which we can bound quadratically the G-game distinguishing number using informations on the classical one. Results on this class are then applied to compute the exact value of the game distinguishing number of hypercubes and even cycles. For the hypercube of dimension 4, determining if D R (Q 4 ) is equal to 2 or 3 remains open.

For odd but not prime cycles, we were also able to compute the exact value of the two game invariants. The Gentle strategy made an intensive use of the imprimitivity of the automorphisms group action. When the cycle is prime, we only know that D G is bounded above by 3. This bound is sharped for small cases. Indeed, D G (C 5 ) = D G (C 7 ) = 3. But, it seems that this is more related to the small size of these cycles than to the primality of their order. Supported by computer experimentation, we state the following conjecture.

Fig. 1 :

 1 Fig. 1: The induced subgraph S in Q5.

Fig. 2 :

 2 Fig. 2: The induced subgraph S in Q4.

Proposition 4 . 1

 41 For n ≥ 6, we have D R (C 2n ) = 2.Proof: Let u, v, w be vertices of C 2n such that d(u, v) = 1, d(u, w) = 3 and d(v, w) = 2. We set S = {u, ū, v, v, w, w} and define the coloring c with 2 colors as follows: c(u) = 1 if u ∈ S and c(u) = 0 otherwise. Let σ be a no trivial colors preserving automorphism. The subgroup < σ > acts on the set of the three blocks contained in S. If σ is an axial symmetry then one block must be stable under σ.

Proposition 4 . 4

 44 If C p is a cycle of prime order p > 5, then D G (C p ) ≤ 3.

Conjecture 5 . 1

 51 If G is a graph with no automorphism of order 2, then D G (G) and D R (G) are both finite.

Acknowledgements

The research was financed by the ANR-14-CE25-0006 project of the French National Research Agency.

Remark that for prime cycles, the automorphisms group action is primitive. It would be interesting to study other graphs for which it is the case. It seems that the question is harder than in the imprimitive case.


Zahraa Yasseen
email: zyasseen@gmail.com

A Verroust-Blondet

A Nasri

Sketch-based 3D Object Retrieval Using Two Views and Visual Part Alignment

Keywords: sketch-based 3D object retrieval, 2D Shape description, Best view selection, Symmetry estimation

Hand drawn figures are the imprints of shapes in human's mind. How a human expresses a shape is a consequence of how he or she visualizes it. A query-by-sketch 3D object retrieval application is closely tied to this concept from two aspects. First, describing sketches must involve elements in a figure that matter most to a human. Second, the representative 2D projection of the target 3D objects must be limited to "the canonical views" from a human cognition perspective. We advocate for these two rules by presenting a new approach for sketch-based 3D object retrieval that describes a 2D shape by the visual protruding parts of its silhouette. Furthermore, the proposed approach computes estimations of "part occlusion" and "symmetry" in 2D shapes in a new paradigm for viewpoint selection that represents 3D objects by only the two views corresponding to the minimum value of each.

Introduction

The two main components of a sketch-based 3D object retrieval application are the 2D shape description method and the 3D object representation. Despite the extensive variety of shape descriptors proposed in 2D shape retrieval context, a relatively small number of ideas have been exploited in sketch-based 3D object retrieval approaches. The most recurrent 2D shape descriptors are the shape context [START_REF] Belongie | Shape context: A new descriptor for shape matching and object recognition[END_REF] and the bag-of-features collected from overlapping areas around densely sampled points in the image [START_REF] Li | Semantic sketch-based 3d model retrieval[END_REF][START_REF] Furuya | Ranking on cross-domain manifold for sketchbased 3d model retrieval[END_REF][START_REF] Eitz | Sketch-based shape retrieval[END_REF]. Despite the acknowledged advantages of accurate numerical models in general shape definition, a looser abstraction of shapes is needed to deal with entries unregulated by delicate measures.

A part-based 2D shape descriptor introduced in [START_REF] Yasseen | Shape matching by part alignment using extended chordal axis transform[END_REF] uses the chordal axis transform [START_REF] Prasad | Rectification of the chordal axis transform skeleton and criteria for shape decomposition[END_REF] (CAT) for shape definition and dynamic time warping (DTW) for matching and distance estimation. On an abstract level, the CAT-DTW descriptor starts by a CAT based segmentation of the silhouette of the 2D shapes. The segments or subregions are embedded in a hierarchy to allow a matching-time selection of visual or protruding parts for optimal correspondence. The visual parts are described by geometric attributes and the spatial relations with other parts. CAT-DTW rectifies the semantic gap between shapes of different natures (see Fig. 1) by taking visual part salience measures relative to the constituting shape and its remaining parts.

The matching method of CAT-DTW calculates the distances between visual parts rather than boundary points using a decision dependant DTW technique that rotates the start point to

Query

Database

Part similarity relative to context find the best match. In this paper, we extend this practice by reversing the direction of search in one of the objects being matched. This reversal allows correct retrievals of similar reflected objects that the original CAT-DTW failed to match. In addition, it facilitates the estimation of the symmetric property of a shape when matched to its inverted version. Distance between a 2D shape and a 3D object is computed by matching the former to a number of 2D projections representing the latter. State of the art methods have gone as far as retaining one hundred projections and some have even exceeded this number. For a sketchbased 3D object retrieval application, in particular, we seriously question the need for such a number. The excessive number of views not only risks run time efficiency degradation, but also increases the possibility of producing views that mislead the retrieval process. A screwdriver, for example, may and should be represented by one view. A snapshot of such an object taken from an angle along its principal axis deceives even a human inspector (see Fig. 2). A table viewed from the top has a similar shape as a book or a door. It is evident that there are more "adequate" views for a given object but whether these are determined by geometric properties or by learning is yet an open issue. In the light of this discussion, we put forward the necessity to investigate viewpoint selection from human cognition theories' perspective.

Cognitive science approaches the viewpoint selection issue by performing case studies to understand the so called "canonical views". In 1981 Palmer et al. [START_REF] Palmer | Canonical perspective and the perception of objects[END_REF] proposed a "maximal information" hypothesis that canonical views are those that give most information about the 3D structure of the object. Blanz et al. [START_REF] Volker Blanz | What object attributes determine canonical views?[END_REF] experimented with digital 3D models asking the partic-ipants to rotate and position objects. They concluded that people would try to avoid occlusion of component and seek pronounced asymmetry. The front or side view of symmetric objects such as teapot, cow, or chair rated lowest amongst the selected views. Recently, Mezuman et al. [START_REF] Mezuman | Learning about canonical views from internet image collections[END_REF] used internet image collections to learn about canonical views and verify precedent theories. Inspired by cognitive science theories, we rely on two concepts to select representative views for a 3D object: minimal part occlusion or maximal information and minimal symmetry. In this paper, we propose methods to quantify these concepts. Taking the projected views from points equidistant to the object's centroid, we relate the level of part occlusion to the sum of lengths of skeletal segments produced by the CAT of each view's silhouette. Symmetry of a given silhouette is estimated by its CAT-DTW distance to its topologically reflected version obtained by a clock-wise (negative direction) traversal of its visual parts.

The rest of the paper proceeds as follows. In section 2, we discuss related work from various aspects. Sections 3 gives an overview of CAT-DTW. A closeup on the details of the DTW technique and the explanation of the topological inversion are presented in section 4. The two-silhouette representation of 3D objects is portrayed in section 5. Evaluation results on SHREC'13 Sketch Track Benchmark and the conclusion follow last.

Related Work

The two major subproblems in sketch-based 3D object retrieval are how to obtain the 3D models' 2D representations and what 2D descriptor to use in the matching process. Existing methods may be classified in many ways depending on different approaches adopted to solve subproblems. For 2D data representation, methods either include shapes' internal available details [START_REF] Sang | Sketch-based 3d model retrieval using diffusion tensor fields of suggestive contours[END_REF][START_REF] Saavedra | Stela: sketchbased 3d model retrieval using a structure-based local approach[END_REF][START_REF] Shao | Discriminative sketch-based 3d model retrieval via robust shape matching[END_REF][START_REF] Saavedra | Sketch-based 3d model retrieval using keyshapes for global and local representation[END_REF][START_REF] Eitz | Sketch-based shape retrieval[END_REF][START_REF] Furuya | Ranking on cross-domain manifold for sketchbased 3d model retrieval[END_REF] or only analyze the outline [START_REF] Ohbuchi | Scale-weighted dense bag of visual features for 3d model retrieval from a partial view 3d model[END_REF][START_REF] Napoléon | From 2d silhouettes to 3d object retrieval: contributions and benchmarking[END_REF][START_REF] Li | Sketch-based 3d model retrieval by incorporating 2d-3d alignment[END_REF][START_REF] Li | Sketch-based 3d model retrieval by viewpoint entropybased adaptive view clustering[END_REF]. The first class of methods incorporate user strokes inside sketched shapes and include suggestive contours [START_REF] Decarlo | Suggestive contours for conveying shape[END_REF], apparent ridges [START_REF] Judd | Apparent ridges for line drawing[END_REF], or other computer generated lines in the 2D views of their 3D models. The second class preprocess their 2D data by diluting and filling operations to have one closed contour line and silhouette per 2D sketch or 3D model projection.

Another aspect to classify methods is the dependance on a training stage using the Bag-of-Words model [START_REF] Eitz | Sketch-based shape retrieval[END_REF][START_REF] Ohbuchi | Scale-weighted dense bag of visual features for 3d model retrieval from a partial view 3d model[END_REF][START_REF] Furuya | Ranking on cross-domain manifold for sketchbased 3d model retrieval[END_REF]. The opposite class makes direct distance estimation between matched objects using either global [START_REF] Sang | Sketch-based 3d model retrieval using diffusion tensor fields of suggestive contours[END_REF] or local [START_REF] Shao | Discriminative sketch-based 3d model retrieval via robust shape matching[END_REF][START_REF] Eitz | Sketch-based shape retrieval[END_REF][START_REF] Ohbuchi | Scale-weighted dense bag of visual features for 3d model retrieval from a partial view 3d model[END_REF], or both global and local [START_REF] Saavedra | Stela: sketchbased 3d model retrieval using a structure-based local approach[END_REF][START_REF] Saavedra | Sketch-based 3d model retrieval using keyshapes for global and local representation[END_REF][START_REF] Napoléon | From 2d silhouettes to 3d object retrieval: contributions and benchmarking[END_REF][START_REF] Li | Sketch-based 3d model retrieval by incorporating 2d-3d alignment[END_REF][START_REF] Li | Sketch-based 3d model retrieval by viewpoint entropybased adaptive view clustering[END_REF][START_REF] Li | Semantic sketch-based 3d model retrieval[END_REF] approaches. Global descriptors define a quantization or a feature vector in R n where the distance metric is defined over that space. Local descriptors represent a shape by a set of feature vectors where the distance is estimated by a minimal cost match between individual features. Methods that use both global and local employ the global descriptor in a pruning stage.

View selection of 3D models has also been tackled in different ways. In general, two motivations have guided this process. The first is to include as many views as feasible so as not to miss a potential viewing angle selected by a human user to draw the object. These methods either select corners and edge midpoints on the bounding box [START_REF] Sang | Sketch-based 3d model retrieval using diffusion tensor fields of suggestive contours[END_REF][START_REF] Saavedra | Stela: sketchbased 3d model retrieval using a structure-based local approach[END_REF][START_REF] Shao | Discriminative sketch-based 3d model retrieval via robust shape matching[END_REF][START_REF] Saavedra | Sketch-based 3d model retrieval using keyshapes for global and local representation[END_REF] or generate uniformly sampled points on the bounding sphere [START_REF] Ohbuchi | Scale-weighted dense bag of visual features for 3d model retrieval from a partial view 3d model[END_REF][START_REF] Li | Sketch-based 3d model retrieval by incorporating 2d-3d alignment[END_REF][START_REF] Furuya | Ranking on cross-domain manifold for sketchbased 3d model retrieval[END_REF] with viewing direction pointing towards the center. The second motivation is to find views more likely to be used by humans and reduce the number of generated images. Napoleon et al. [START_REF] Napoléon | From 2d silhouettes to 3d object retrieval: contributions and benchmarking[END_REF] first align the model and then take only up to 9 projections. Eitz et al. [START_REF] Eitz | Sketch-based shape retrieval[END_REF] employ Support Vector Machine with a radial basis function kernels to learn a "best view classifier" during the training stage and use it in the testing stage. Li et al. [START_REF] Li | Sketch-based 3d model retrieval by incorporating 2d-3d alignment[END_REF] use the View Context similarity between the sketch and saved projections to prune unlikely views in an alignment stage. In a later publication, and following the observation that not all 3D models views are equally important, Li et al. [START_REF] Li | Sketch-based 3d model retrieval by viewpoint entropybased adaptive view clustering[END_REF] propose a complexity metric based on viewpoint entropy distribution. The idea is to assign more views for more complex objects and thus recommend class-specific numbers of projections.

A recent family of methods has emerged characterized by employing machine learning methods to bridge the semantic gap between sketches and projection images. Li et al. [START_REF] Li | Semantic sketch-based 3d model retrieval[END_REF] use a Support Vector Machine with radial basis function kernel to build a classifier that predicts the possibilities of the input sketch belonging to all the categories. Furuya et al. [START_REF] Furuya | Ranking on cross-domain manifold for sketchbased 3d model retrieval[END_REF] use a semisupervised machine learning method called Manifold Ranking Algorithm [START_REF] Zhou | Learning with local and global consistency[END_REF]. The algorithm works by diffusing relevance value from the query to the 3D models in a Cross-Domain Manifold the two domains being sketches and 3D models.

Since year 2012, sketch-based 3D shape retrieval contests (SHREC) are being held on yearly basis [START_REF] Li | Shrec'12 track: Sketch-based 3d shape retrieval[END_REF][START_REF] Li | Shrec'13 track: Large scale sketch-based 3d shape retrieval[END_REF][START_REF] Li | A comparison of methods for sketch-based 3d shape retrieval[END_REF][START_REF] Li | Extended large scale sketch-based 3d shape retrieval[END_REF]. A participating group would contribute in more than one run showing results of different parameter settings or choice of particular algorithms. It is notable that there is a small range of 2D shape descriptors tested in sketch-based 3D object retrieval compared to the much larger number of available choices. The 2D shape descriptor that we employ in this paper uses a skeleton to represent shapes by visual parts and their spacial relationships.

2D Shape Description

In order to keep this paper as self contained as possible, we give an overview of the CATbased shape description method. However, more details can be found in the original CAT-DTW documentation [START_REF] Yasseen | Shape matching by part alignment using extended chordal axis transform[END_REF].

The input data is a binary image representing the silhouette of a single object. We extract the contour, locate corner points, and sample the in-between contour fragments uniformly. The advantage of locating corner points is the inclusion of the sharp features in the sample set. The region is then triangulated using Constrained Delaunay Triangulation (CDT). The rectified CAT and a set of pruning and merging operations provide a skeleton with an association between skeletal segments and subregions (see Fig. 3(a)). Subregions are categorized according to their connectivity into three types: terminal, sleeve, and junction characterized by one, two, and many connected segments respectively.

The CAT segments are embedded in a tree where leaf nodes correspond to terminal segments (see Fig. 3(b)). We leave out the process that locates the root of the tree since it does not influence the course of this paper. Our main concern is the visual parts of the shape and how they are represented in this hierarchy. First, terminal nodes with relative size, eccentricity, and convexity beyond some thresholds are labeled as salient nodes. Starting from the bottom of the tree, the visual parts of the shape are represented by all subtrees that constitute less than two salient nodes. Visual parts that contain more than one node in their subtrees represent a set of CAT segments joined into one higher level entity denoted by a wing node (see Fig. 3).

The visual parts, comprised of terminal and wing nodes that we denote by feature nodes, are kept in their anti-clockwise order of appearance along the boundary of the object. Each node is described by 9 geometric attributes: area, perimeter, eccentricity, circularity, rectangularity, convexity, solidity, bending energy, and chord length ratio in addition to a radial distance signature. These values are combined into a feature vector v that is made of two parts: geometric parameters p and the radial distance signature r. The distance between two vectors v 1 and v 2 is the Euclidian distance between the parameters plus the squared distance between the signature part.

d(v 1 , v 2 ) = sqrt [ 9 ∑ i=1 (p 1 [i] -p 2 [i]) 2 ] + 15 ∑ i=1 (r 1 [i] -r 2 [i]) 2 (1)
Similarly, the norm of the feature vector is given by:

|v| = sqrt [ 9 ∑ i=1 p[i] 2 ] + 15 ∑ i=1 r[i] 2 (2)
(a) The CAT and the subsequent segmentation.

(b) Marked subtrees correspond to wing nodes. The leaves are arranged from left to right in the anticlockwise order of appearance along the boundary of the shape.

(c) Visual parts represented by terminal nodes on the finest level of detail (left) and by wing nodes on higher levels. More than two salient nodes cannot be included in the same wing (right) and thus stop the process of wing node formation. The spatial and angular distances between feature nodes comprise an inter-distance matrix relating every pair of them. An entry (i, j) in this matrix is a 3 dimensional vector (d E , d BE , dA) corresponding to Euclidian distance, bending energy, and angular distance between nodes i and j.

Adapted Dynamic Time Warping Method

Dynamic time warping is a method that originated in the context of aligning voice signals with different time latency [START_REF] Vintsyuk | Speech discrimination by dynamic programming[END_REF]. Later on, it was introduced to the shape matching world to measure distance between closed shapes. Roughly, the idea is to rotate one shape while calculating a distance matrix for every obtained alignment. Each row corresponds to the distance between a point in the first shape and all points in the other. A minimal distance path is calculated for every matrix resulting in a point-to-point or point-to-segment pairing. The matrix that produces the minimal distance among others represents the best alignment.

The feature nodes are represented in a feature space of dimension N (N = 24) comprised of an assembly of geometric parameters. Every object has an ordered set of feature vectors in addition to an inter-distance matrix. To match two shapes A and B, we seeks a set of pairs associating feature nodes from A and B. The couples correspond to non-overlapping visual parts and must not violate their anti-clockwise ordering. The cost of a match is defined by the sum of the following values:

1. The distance defined in Eq. 1 between coupled feature nodes from A and B. 2. For every consecutive couple (q (q∈A) , r (r∈B) ) and (s (s∈A) , t (t∈B) ), the internal distance defined by: (d

E (q, s) -d E (r, t)) 2 + (d BE (q, s) -d BE (r, t)) 2 + (d A (q, s) -d A (r, t)) 2 3.
Terminal nodes that are not included in the match cost a penalty equal to the norm in Eq. 2.

Every terminal node in each object is a potential starting point for the anti-clockwise traversal of feature nodes. To find the optimal solution, we compute the minimal cost matches for all possible combinations of starting terminal nodes of the two shapes. However, due to their relation with wing nodes, some terminal nodes are excluded from the set of candidate start points. In the following sections, we describe what viable configurations are and how the cost matrix is built and handled.

Generating Viable Configurations

Wing nodes are visual features that must be considered for matching as a whole in any tested configuration. A terminal node selection as the starting point should not cause any of its related wing nodes to be split between the beginning and the end of the list of feature nodes. This observation leads to the introduction of the stop point which is a terminal that has either one of the following properties:

• It does not belong to any wing node.

• It is the first terminal node to appear in the anti-clockwise direction in all the wings it belongs to.

Different configurations are generated by alternately shifting one object's start node to the next stop point while fixing the other.

Decision-based Dynamic Time Warping

Every configuration provides two ordered sequences of feature nodes to be matched. The dynamic time warping technique finds the minimal cost path by setting up a matrix of all possible matches. Starting from (n, m) towards (0, 0), the cost of the optimal path is accumulated following the minimal cost path rule defined by: cost(i, j) = cost(i, j) + min(cost(i + 1, j + 1), cost(i + 1, j), cost(i, j + 1)) Our variation of the solution follows from the specifics of the problem.

We construct an n × m matrix where n and m are the numbers of terminal nodes of the two shapes. Every entry in this matrix contains a decision node that enumerates all possible options that can be taken when the entry is reached. The decision node compares the cost of a terminal-terminal, terminal-wing, wing-terminal, wing-wing, and a void match. The void match is the decision to exclude one or both of the terminals from the matching process. This list of options is not independent from its surrounding matrix entries. For example, a wingwing matching decision affects the matrix block spanned by the terminals constituting these two wings (see Fig. 4). This slightly alters the minimal cost path rule since at (i, j), the "previous" entry is not simply either one of (i + 1, j + 1), (i + 1, j), or (i, j + 1). It is rather related to the option at hand and the block of matrix spanned by the nodes being matched according to this option. After all decision nodes have selected their minimal cost option, the optimal cost of the current configuration is found in the minimal cost at entry (0, 0).

Topological Inversion

As described so far, CAT-DTW works well on Kimia-99 and Kimia-216 2D shape datasets [START_REF] Sebastian | Recognition of shapes by editing their shock graphs[END_REF]. However, it happens that these datasets do not include reflected instances of the same class. For example, the correct match between the shapes shown in Fig. 5 will never be found using the current CAT-DTW. The visual parts of these two objects are arranged in reversed orders: head, tail, hind legs, front legs for the first object and head, front legs, hind legs, tail for the second. Reversing the direction of terminal traversal for one of the objects allows obtaining the configuration that would give the optimal match as shown in Fig. 5. When an object is matched to its inverted version, the distance is an estimate of the degree of symmetry. Smaller values indicate stronger symmetric property of the shape (some examples are shown in Fig. 6). We call the inverse of this distance the symmetry measure and use it to find asymmetric projected views of 3D objects as shown in the next section.

3D Object's Representative Views

We take projected images of the 3D object from 50 views positioned on the unit sphere bounding the object and pointing towards its center. First, the object is scaled and translated to lie within a cube half the size of the unit cube. Then one Catmull-Clark subdivision [START_REF] Catmull | Recursively generated b-spline surfaces on arbitrary topological meshes[END_REF] step is applied to the cube producing a volume defined by 26 vertices and 24 faces. The vertices and the centroids of the faces are translated in the radial direction so that they all lie on the unit sphere and equidistant from the origin. Each viewpoint gives a binary silhouette representation of the 3D object.

When humans design sketches to represent an object, they tend to make all the meaningful salient parts of the object visible (the four legs of the cow/horse, the legs of a chair, etc.) even if the perspective view of the object is altered. This is a demonstration of the "minimal part occlusion" theory proposed as one of the "canonical views" criteria. Following this observation, we select the silhouettes having the greater skeletal length which we compute as the sum of skeletal segments of terminal and sleeve nodes and the maximal three skeletal segments of junction nodes. The silhouettes with top k skeletal lengths (k equal to 10 in our experiments)

The decision matrix where a row (respectively column) corresponds to a terminal in the first (respectively second) object. Each entry (i, j) holds all possible pairings between the visual parts related to the terminals associated to row i and j.

(c) The minimum cost path in the matrix and the consequent part correspondence between the matched shapes.

Figure 4: The optimal correspondence between two shapes obtained from the minimal cost path in the distance matrix. Note how the 9 th option at entry (0, 0) shown in Fig. 4(b) gives a minimal cost and leads to the pairing highlighted in purple in Fig. 4(c).

+ -+ +

Figure 5: Applying DTW to find part correspondence between the objects shown top row where the visual parts' orderings are horn, tail, hind leg, ..., horn and horn, horn, front leg, ..., tail respectively. The method matches the heads correctly due to rotating the start point of the second object so as to have the two horns adjacent. However, due to reflectance, other parts are mismatched. The third row shows the where the second object is arranged in the reverse direction. The total distance obtained in this setting is minimal and the visual parts are paired more accurately.

8.78 0.5 12.5 1.5 are selected into a candidate set S k and the rest are discarded (see Fig. 7). Two silhouettes remain to be selected from S k such that the first is the one with maximal skeletal length and the second has minimal symmetry measure.

Experimental Results and Discussion

We tested the 2D shape descriptor and our view selection paradigm on the testing datasets of the SHREC'13 Sketch Track Benchmark [START_REF] Li | Shrec'13 track: Large scale sketch-based 3d shape retrieval[END_REF]. Our 2D shape descriptor handles closed shapes with no holes. For both the sketches and 3D models' projections, we perform filling operations to produce a single contour for analysis. Moreover, we apply a series of erosion and filling operations on sketches to amend disconnected boundary lines and give more emphasis to strokes expressing thin features such as tails or antennas (see Fig. 8). When surrounding entities are sufficiently disconnected from the main depicted object (see the barn in Fig. 8), they are discarded by taking the extracted boundary line that has the greatest length. This works well with this sketch dataset since it happens that in such cases, secondary entities are drawn smaller than the main object.

We employ the seven performance metrics adopted in SHREC'13 [START_REF] Li | Shrec'13 track: Large scale sketch-based 3d shape retrieval[END_REF]. They are Precision-Recall (PR) diagram, Nearest Neighbor (NN), First Tier (FT), Second Tier (ST), E-Measures (E), Discounted Cumulated Gain (DCG) and Average Precision (AP). To compute these metrics, we use the evaluation code available from the contest's website. Table 1 shows that our approach outperforms the methods tested on the same benchmark except for those that employed machine learning by cross-domain manifiold ranking (CDMR). However, the average response time per query of our method is 27.79 seconds on an Intel Core i7 3632QM @ 2.20GHz 8GB RAM while the CDMR employing methods exceed 600 seconds on an Intel Core i7 3930K @ 3.20GHz 64GB RAM. In addition, the precision recall plot in Fig. 9 shows that our method performs best amongst its peers.

Compared to other methods that participated in this track, Saavedra et al [START_REF] Saavedra | Sketch-based 3d model retrieval using keyshapes for global and local representation[END_REF] use the least number of sample views for a 3D model. They use the 6 orthogonal views (top, bottom, left, right, front, and back). However, their method's performance evaluation reveals the shortcomings of this choice. It is evident that without a suitable alignment method, the orthogonal views of a 3D object cannot give any guarantees that they include a canonical view as visualized, and consequently depicted, by humans. Despite increasing the number of views to 26, Aono et al. [START_REF] Aono | 3d shape retrieval from a 2d image as query[END_REF] still score lowest on the precision recall plot diagram. On the other hand, Li et al. [START_REF] Li | Sketch-based 3d model retrieval by incorporating 2d-3d alignment[END_REF] (SBR-2D-3D-NUM-50) start form 81 sample views for each 3D object and attempt to align each to the query sketch retaining the best 4 candidates. In another method (SBR-VC-NUM) [START_REF] Li | Sketch-based 3d model retrieval by viewpoint entropybased adaptive view clustering[END_REF], they drop the alignment stage and keep a precomputed number of sample views per class. The performance improvement of this method (SBR-2D-3D-NUM-50 to SBR-VC-NUM-50) is negligible. Furuya et al. [START_REF] Furuya | Ranking on cross-domain manifold for sketchbased 3d model retrieval[END_REF] use the highest number of views proposed in this field (162 views) and still need machine learning to improve their retrieval results increasing the retrieval time in an enourmous leap (0.49 seconds for BF-fGALIF to 615.95 seconds for CDMR-BF-fGALIF).

Reporting better performance over these methods while using only two sample views, we verify the merit of the "informative" and "asymmetric" criteria in viewpoint selection. In addition, two other hypothesis are supported by these results. The first one is the logical opposite of more views implying better performance. On the contrary, there are incorrect views for 3D models that cause misinterpretation and mismatching and thus must be eliminated from its set of sample views. The second hypothesis is the propriety of a visual part-based shape descriptor for a query-by-sketch retrieval of 3D objects. This does not draw from the performance metrics alone but rather from the fact that this descriptor behaves poorly with classes characterized by weak part salience. Nonetheless, it still managed to compensate this setback and produce overall better results.

Conclusion

We proposed a sketch-based 3D object retrieval approach that outperforms the methods that contributed in SHREC'13 [START_REF] Li | Shrec'13 track: Large scale sketch-based 3d shape retrieval[END_REF] on the testing dataset of the Sketch Track Benchmark. We showed that a descriptor based on salient parts, their relative sizes and protrusion angles is essential to match conceptually similar but precisely dissimilar objects, which is the case with sketch-based retrieval applications. In addition, we demonstrated that an excess in 2D representations of 3D objects has a potentially degrading effect on the performance results of any method. We made intra-object matches between its projections and composed criteria based on the notion of informative and asymmetric views to represent the object by only two views.

The system at hand is liable to many improvements subject to further experiments. Throughout its successive stages other methods for sampling, segmentation, shape signatures, and part correspondence can be tested. The devised algorithm generates all possible configurations and search for the optimal match of each. Many methods for complexity reduction have been proposed in the general framework of DTW [START_REF] Al-Naymat | Sparsedtw: A novel approach to speed up dynamic time warping[END_REF][START_REF] Wang | Experimental comparison of representation methods and distance measures for time series data[END_REF][START_REF] Salvador | Toward accurate dynamic time warping in linear time and space[END_REF][START_REF] Lemire | Faster retrieval with a two-pass dynamic-time-warping lower bound[END_REF]. In addition to these methods, some pruning strategies can be applied to avoid the detailed correspondence computations for each configuration.

Figure 1 :

 1 Figure 1: Matching a sketched human stick-figure (after applying erosion and filling) to the silhouettes of 3D models' projections.

Figure 2 :

 2 Figure 2: Recognizable (top) and misleading (bottom) views of 3D objects.

Figure 3 :

 3 Figure 3: The visual parts embedded in a hierarchical structure. The tree nodes in Fig. 3(b) are shaded with the same color of their corresponding subregion in Fig. 3(a).

( a )

 a Configuration where the start points are the snouts in both cats.(

Figure 6 :

 6 Figure 6: Symmetric shapes and their associated asymmetry evaluation. Lower values indicate stronger symmetry.

Figure 7 :

 7 Figure 7:The silhouettes with the top 20 skeletal lengths. For each object, the representative views are the one with maximal skeletal length (first silhouette in the column) and the silhouette with minimal symmetry selected from the top 10 skeletal lengths (marked by the red box).

Figure 8 :

 8 Figure 8: Contour line extraction of sketched images.

Figure 9 :

 9 Figure 9: Precision-Recall diagram performance comparisons on the testing datasets of the SHREC'13 Sketch Track Benchmark.

Table 1 :

 1 Performance metrics for the performance comparison on the testing dataset of the SHREC'13 Sketch Track Benchmark.

	PARTICIPANT	METHOD	NN FT	ST	E	DCG AP
	Aono, Masaki [2]	EFSD	0.023 0.019 0.036 0.019 0.24	0.031
	Li, Bo [14]	SBR-2D-3D-NUM-50	0.132 0.077 0.124 0.074 0.327 0.094
	Li, Bo [17]	SBR-VC-NUM-100	0.164 0.097 0.149 0.085 0.348 0.113
		SBR-VC-NUM-50	0.132 0.082 0.131 0.075 0.331 0.098
	Saavedra, Jose M. [24] FDC	0.053 0.038 0.068 0.041 0.279 0.051
	Furuya [8]	BF-fGALIF	0.176 0.101 0.156 0.091 0.354 0.119
		BF-fGALIF+BF-fDSIFT	0.213 0.123 0.186 0.107 0.379 0.143
		CDMR-BF-fGALIF	0.242 0.174 0.263 0.146 0.427 0.215
		CDMR-BF-fGALIF+CDMR-BF-	0.279 0.203 0.296 0.166 0.458 0.246
		fDSIFT
		UMR-BF-fGALIF	0.159 0.119 0.179 0.102 0.367 0.131
		UMR-BF-fGALIF+UMR-BF-fDSIFT	0.209 0.131 0.195 0.113 0.386 0.152
	Our method	CAT-DTW	0.220 0.122 0.180 0.101 0.379 0.128