Marie Babel
email: mbabel@insa-rennes.fr

Olivier Déforges
email: odeforges@insa-rennes.fr

LOSSLESS AND LOSSY MINIMAL REDUNDANCY PYRAMIDAL DECOMPOSITION FOR SCALABLE IMAGE COMPRESSION TECHNIQUE

We present a new scalable compression technique dealing simultaneously with both lossy and lossless image coding. An original DPCM scheme with refined context is introduced through a pyramidal decomposition adapted to the LAR (Locally Adaptive Resolution) method, which becomes by this way fully progressive. An implicit context modeling of the prediction errors, due to the low resolution image representation including variable block size structure, is then exploited to the for lossless compression purpose.

INTRODUCTION

Recently, many techniques have been developed in the field of lossless compression of greyscale images. The state-ofthe art mentions the use of predictors or reversible transforms. Moreover, standards using predictions schemes are mostly non-scalable, such as the well-known CALIC method [START_REF] Wu | A context-based, adaptive, lossless/nearly-lossless coding scheme for continuoustone images[END_REF]. Nevertheless, S+P [START_REF] Said | Reversible image compression via multiresolution representation and predictive coding[END_REF] algorithm proposes a multiresolution decomposition of images, combining S-Transform and prediction.

Besides, TMW [START_REF] Meyer | TMW : a new method for lossless image compression[END_REF] introduced the interesting principle of a description for an image in two parts. By this way, images are considered to be the superposition of the global information and the texture (local information). This concept allows us to provide either a lossy (first part of the message) or a lossless compression (second part, corresponding to the error image).

The LAR (Locally Adaptive Resolution) [START_REF] Deforges | Region of interest coding for low bit-rate image transmission[END_REF] based on a variable block-size decomposition and leading to an efficient lossy image compression technique is shown in the first section. The purpose of this paper is to present a new lossless and lossy image coding, given by the improvement of the LAR coder, that combines both prediction (DPCM scheme) and scalability. Section 3 defines a minimal-redundancy pyramidal decomposition that allows a progressive reconstruction at the decoder. The last part of this paper presents the lossless system of coding, that takes advantage of the implicit context modeling property of our decomposition for entropy encoding.

LAR METHOD FOR GREYSCALE IMAGES

The LAR compression method -designed first for lossy greyscale images coding -is a two-layer codec : a spatial codec and a complementary spectral one. The spatial coder provides a low bit rate compressed image whereas the spectral one encodes the texture. The LAR method was also extended for region-based color image coding. Furthermore the quality of the low resolution LAR image has been evaluated and recognized to be better than Jpeg-2000 [START_REF] Deforges | Region of interest coding for low bit-rate image transmission[END_REF].

Spatial coder

The basic idea is that the local resolution, i.e. the pixel size, can depend on the local activity. This leads to construct a variable image resolution, determined by means of a quadtree data structure. The final size of pixels (from 16 × 16 to 2 × 2) is defined thanks to a local gradient estimation : each block is reconstructed by its average luminance. Through this decomposition, the pixel size gives implicitly the nature of the blocks : indeed, small ones are located on contours whereas large ones are situated on smooth areas (Fig. 1). Consequently, a coarse edge-driven segmentation map is automatically available at both the coder and the decoder. This image content information controls a psychovisual quantization of the luminance : large squares require a fine quantization (in uniform areas, human eyes are strongly sensitive to brightness variations) and small ones can support a coarse quantization (low sensitivity). Perceptible blocks artifacts in homogenous areas are easily removed by a simple but efficient post-processing based on an adaptive linear interpolation.

To sum up, this coder has mainly two distinctive characteristics : on one hand, we have a very fast and efficient technique for high compression ratio, and on the other hand, the method simplifies the image source by removing the local texture while preserving the objects boundaries.

Spectral coder

In order to obtain higher image quality, the texture (whole error image) can be encoded by the spectral coder that uses a DCT adaptive block-size approach [START_REF] Chen | Adaptive transform coding via quad-tree based variable block-size DCT[END_REF]. Both the size and the DC components are here provided by the first coder. The use of adapted square size allows a content-based scalable encoding scheme : for example, edge enhancement can be made only by transmitting the AC coefficients of small blocks.

LOSSY PYRAMIDAL PREDICTIVE DECOMPOSITION

In this section we present the new progressive approach, that combines prediction (DPCM) and pyramidal decomposition. This leads to construct a scalable LAR spatial coder.

Prediction algorithm

The actual spatial LAR coder encodes in one pass (raster scan) the intensity block values by means of the Gradient Adjusted Predictor (GAP) [START_REF] Wu | A context-based, adaptive, lossless/nearly-lossless coding scheme for continuoustone images[END_REF]. The new scalable DPCM scheme is based on the predictor described in [START_REF] Wu | Lossless Compression of Continuous-Tone Images, via Context Selection, Quantization and Modelling[END_REF] by Wu.

For full resolution image, errors are coded by means of three interlaced sampling of the original image. By this way, we tend to obtain a spatial configuration of 360 ˚type context surrounding a given pixel. The general principle is as follows (Fig. 2) : the first pass encodes a uniform subsampled image formed by the average of two diagonally adjacent pixels through a classical DPCM system. Then the second pass provides the values of the two pixels used to compute the previous image. At this stage, the prediction 360 ˚type context consists in the already known values of the current pass and the diagonal means coded by the first pass. Finally, the third pass encodes the remaining half of the original image. Once again, thanks to the reconstructed pixels, a completely spatially enclosing and adjacent context is available to predict the modeled pixel.

Minimal redundancy pyramidal decomposition

We propose to extend the previous full resolution scanning scheme to get a pyramidal representation of the image.

Bottom-Up building. Four blocks N 2 × N 2 are gathered into one block N × N valued by the average of the two blocks of the first diagonal (Fig. 3). By this way, the value of a N × N is equal to the average over the whole diagonal in the full resolution image. The highest level (level 4) of the pyramid corresponds to the 16×16 blocks (largest block size in the LAR method). Top-Down decomposition. Let the original image be of width W and height H, the first stage of our pyramid concerns the image of size W/16 × H/16 (level 4). The first pass of the Wu algorithm (simple causal DPCM coding of the block values) is applied. Then, each square is split until its maximal size is reached. For a given level (block size) of the pyramid, the blocks of smaller or equal size are successively processed by passes 2 and 3. The values of higher size blocks are copied out in order to refine the context (Fig. 4) .

By this way, taking into account the variable resolution LAR image, a progressive content-based method is developed : if a restricted context is sufficient for the large blocks, a more accurate and informative context exists for the small blocks (objects boundaries). The main property of this method is that the redundancy is minimal. Indeed, for a group of four blocks obtained by splitting a block from the above level, the diagonal mean is already known. Thus, a single bit is required to reconstruct the second of the two di- Note that this pyramidal decomposition modify the initial LAR representation where each block value is the average of all pixels within this block. Nevertheless, a slight difference is introduced. Indeed, except from the 2 × 2 blocks, all the blocks correspond to flat areas (by construction), and the average luminance of whole pixels is quite similar to the diagonal pixels average (Fig. 5).

Experimental results

The table 1 gives the entropies resulting from the pyramidal approach compared to the ones obtained by the original

SCALABLE LOSSLESS CODING

The previous stage provides a low resolution image. It also separates two types of blocks :

-flat areas in all N × N blocks with N ∈ {4, 8, 16}, characterized by a low entropy, -contour areas in 2 × 2 blocks, characterized by an high entropy.

The extension of the method to a lossless scheme consists in coding the error image (texture) which results from the LAR compressed image and the original one. Each N × N block in the LAR representation is decomposed until full resolution according to our pyramidal decomposition principle. Next sub-section deals more particulary with the separation of the entropy into different laws.

Entropy laws and implicit context modeling

Global entropy can be reduced when different classes of symbols following the same law can be isolated. This principle is often used in lossless coding methods through the context modeling technique [START_REF] Wu | A context-based, adaptive, lossless/nearly-lossless coding scheme for continuoustone images[END_REF] : a local estimation of a pixel activity leads to its classification into one a priori law.

Our method provides a straightforward separation of the laws at two different levels :

-from the block size : 2 × 2 blocks are located on strong edges in the image inducing an high average entropy error, whereas other blocks contain local homogenous texture, -from the several passes of each decomposition level : the bit resulting from the diagonal mean is transmitted separately. Values from passes 2 and 3 significantly differ.

The table 2 gives an example of the final entropy, when separating the LAR representation, texture and passes 2 and 3 error values. The last level (full resolution) distinguishes the 2 × 2 blocks from the others. This divided bitstream gives much more interesting results than a global coding (Tab. 3). Actually, an implicit context modeling is made, due the fact that the quad-tree decomposition is already content based. The table 3 presents also the result of the application of the CALIC algorithm on the images. One can see that this the state-of-the-art method is a bit better than our compression scheme, but our pyramidal approach has the advantage to be spatially scalable.

Influence of the LAR parameter

The threshold of the morphological gradient is the unique parameter. It determines the quantity of information respectively allocated to low resolution image and texture. The figure 6 gives the entropy of Lena image when this threshold varies. One can see that the dispersion of the resulting values is small for a given range of thresholds. Thus, the method is not very sensitive to this parameter : it can then be a priori fixed.

CONCLUSION AND PERSPECTIVES

This paper has presented an original technique for scalable lossy and lossless compression. The knowledge of the quadtree data structure is sufficient to improve significantly the compression ratio for the lossless coding, by gathering and coding separately the information of the same nature. By means of an unique algorithm, one can choose either a lossy or a lossless image coding. The configuration of the codec is simplified since the choice of the gradient estimation parameter has no significant impact on the bit rate. Moreover, the properties of the previous LAR coder are kept. The scalability here introduced in the scheme extend the possibilities of the codec. Future research will be made in the adaptation of the prediction according to the nature of the information (contours or texture).

Fig. 1 .

 1 Fig. 1. (a) Original image. (b) Variable block sizes representation (subsampled grid : 0.032 bpp).

Fig. 2 .

 2 Fig. 2. Wu algorithm : 3 passes and prediction neighborhood

Fig. 3 .

 3 Fig. 3. Bottom-up building.

Fig. 4 .

 4 Fig. 4. Block values to be predicted

Fig. 5 .

 5 Fig. 5. (a) Original image. (b) Low resolution initial LAR image. (c) Low resolution new LAR image. (d) Post-processed new LAR image

Fig. 6 .

 6 Fig. 6. Influence of the gradient threshold.

Table 1 .

 1 scheme. One can observe that the entropy is equivalent for both techniques, but now the encoding scheme is scalable. Compression results for low resolution image (LAR coder) : original and new method.

		Entropy (bit per	Global entropy
			block)		(bpp)
	Image name Initial	New	Initial	New
	Baboon	6.73	6.79	1.05	1.06
	Barb	6.45	6.54	0.67	0.68
	Bike	6.68	7.17	0.41	0.44
	Cafe	6.80	7.12	0.84	0.88
	Finger	6.51	6.46	1.36	1.35
	Hotely	6.25	6.61	0.52	0.55
	Lena	6.17	5.98	0.32	0.33
	Zelda	5.81	6.15	0.17	0.18

Table 2 .

 2 Lossless coding of Lena image.

Table 3 .

 3 Compression results for lossless coding of images.

			Entropy (bpp)
	Image	Proposed	Proposed	CALIC
		(1 law)	(sev. laws)
	Baboon	7.02	6.09	6.14
	Barb	5.88	5.02	4.93
	Bike	5.40	4.63	4.53
	Cafe	6.41	5.50	5.37
	Finger	6.56	5.75	5.52
	Hotely	5.66	4.89	4.56
	Lena	5.07	4.40	4.33
	Zelda	4.80	4.21	3.98
	Average	5.85	5.06	4.92


Pierre Dehornoy
email: pierre.dehornoy@ujf-grenoble.fr

Tali Pinsky

CODING OF GEODESICS AND LORENZ-LIKE TEMPLATES FOR SOME GEODESIC FLOWS

Coding of geodesics and Lorenz-like templates for some geodesic flows

Pierre Dehornoy, Tali

Introduction

For p, q, r three positive integers-r being possibly infinite-satisfying 1 p + 1 q + 1 r < 1, we consider the associated hyperbolic triangle and the associated orientation preserving Fuchsian group G p,q,r . The quotient H 2 /G p,q,r is a sphere with three cone points of angles 2π p , 2π q , 2π r obtained by gluing two triangles. The unit tangent bundle T 1 H 2 /G p,q,r is a 3-manifold that is a Seifert fibered space. It naturally supports a flow whose orbits are lifts of geodesics on H 2 /G p,q,r . It is called the geodesic flow on T 1 H 2 /G p,q,r and is denoted by ϕ p,q,r . These flows are of Anosov type [START_REF] Anosov | Geodesic flows on closed Riemannian manifolds with negative curvature[END_REF] and, as such, are important for at least two reasons: they are among the simpliest chaotic systems [Had1898] and they are fundamental objects in 3-dimensional topology [START_REF] Thurston | On the geometry and dynamics of diffeomorphisms of surfaces[END_REF]. Each of these flows has infinitely many periodic orbits, which are all pairwise non-isotopic. The study of the topology of these periodic orbits began with David Fried who showed that many collections of such periodic orbits form fibered links [START_REF] Fried | Transitive Anosov flows and pseudo-Anosov maps[END_REF]. More recently Étienne Ghys gave a complete description in the particular case of the modular surface-which corresponds to p = 2, q = 3, r = ∞by showing that the periodic orbits are in one-to-one correspondence with periodic orbits of the Lorenz template [START_REF] Ghys | Knots and dynamics[END_REF].

The goal of this paper is to extend this result by giving an explicit description of the isotopy classes of all periodic orbits of ϕ p,q,r for every p, q, r (with p, q finite). A template [START_REF] Birman | Knotted periodic orbits in dynamical systems-I: Lorenz's Equations[END_REF] is an embedded branched surface made of several ribbons and equipped with a semi-flow. A template is characterized by its embedding in the ambient manifold and by the way its ribbons are glued, namely by the kneading sequences that describe the left-and rightmost orbit of every ribbon [START_REF] Hubbard | The classification of topologically expansive Lorenz maps[END_REF][START_REF] De | One-Dimensional Dynamics[END_REF]. Call T p,q,r the template with two ribbons whose embedding in T 1 H 2 /G p,q,r is depicted on Figure 1 and whose kneading sequences are the words u L , u R , v L , v R given by Table 1, where the letter a corresponds to travelling along the left ribbon and b to travelling along the right ribbon. If r is infinite, the template is open of both sides of every ribbon, so that the kneading sequences are not realized by any orbit of the template. If r is finite, both ribbons are closed on the left and open on the right, so that u L and v L are realized, but not u R nor v R .

Theorem A. Up to one exception when r is finite, there is a one-to-one correspondance between periodic orbits of the geodesic flow ϕ p,q,r on T 1 H 2 /G p,q,r and periodic orbits of the template T p,q,r such that its restriction to every finite collection is an isotopy. The exception consists of the two orbits of T p,q,r whose codes w L and w R are given by Table 2 and which actually correspond to the same orbit of ϕ p,q,r .

p-1 q-1 r-1 u L v R v L u R Figure 1
. The template T p,q,r in T 1 H 2 /G p,q,r . The 3-manifold T 1 H 2 /G p,q,r is obtained from S 3 by surgeries on a three component Hopf link (dotted) with the given indices. The template T p,q,r is characterized by its embedding in T 1 H 2 /G p,q,r and by the kneading sequences that describe the orbits of the extremities of the ribbons. When r is infinite, T 1 H 2 /G p,q,r is the open manifold obtained by removing the component labelled r -1 of the 3-component Hopf link. When p = 2, the exit side of the left ribbon is strictly included into the entrance side of the right ribbon.

In subsequent works, we intend to use the template T p,q,r for deriving important properties of the geodesic flow ϕ p,q,r , in particular the fact that all periodic orbits form prime knots, or the left-handedness (a notion introduced in [Ghy09]) of ϕ p,q,r (see ).

The kneading sequences (Table 1) may look complicated. In a sense, it is the cost for having a template with two ribbons only. The proof suggests that, in the case of r finite, there are infinitely many other possible words, thus leading to other templates (the difference lying in the kneading sequences, not in the embedding). But these words are not simpler than the ones we propose here.

Theorem A is to be compared with previous works by Ghys [START_REF] Ghys | Knots and dynamics[END_REF], Pinsky [START_REF] Pinsky | Templates for the geodesic flow[END_REF], and Dehornoy [START_REF] Dehornoy | Geodesic flow, left-handedness, and templates[END_REF]. The results of [START_REF] Ghys | Knots and dynamics[END_REF][START_REF] Pinsky | Templates for the geodesic flow[END_REF] deal with orbifolds of type H 2 /G 2,3,∞ and H 2 /G 2,q,∞ for all q 3 respectively. The existence of a cusp in these cases allows the obtained templates to have trivial kneading sequences of the form a ∞ and b ∞ . These 2. The codes of the two periodic orbits of T p,q,r that correspond to the same periodic orbit of the geodesic flow ϕ p,q,r .

u L v R r infinite (a p-1 b) ∞ (b q-1 a) ∞ p, q, r > 2 r odd ((a p-1 b) r-3 2 a p-1 b 2 ) ∞ ((b q-1 a) r-3 2 b q-1 a 2 ) ∞ r even ((a p-1 b) r-2 2 a p-2 (ba p-1 ) r-2 2 b 2 ) ∞ ((b q-1 a) r-2 2 b q-2 (ab q-1 ) r-2 2 a 2 ) ∞ p = 2, q > 2, r > 4 r odd ((ab) r-3 2 ab 2 ) ∞ b q-1 ((ab q-1 ) r-5 2 ab q-2 ) ∞ r even ((ab) r-4 2 ab 2 ) ∞ b q-1 ((ab q-1 ) r-4 2 ab q-2 ) ∞ v L := bu L , u R := av R Table 1. The kneading sequences of the template T p,q,r . p, q, r > 2 w L w R r odd ((a p-1 b) r-3 2 a p-2 b) ∞ ((b q-1 a) r-3 2 b q-2 a) ∞ r even ((a p-1 b) r-2 2 a p-2 b(a p-1 b) r-4 2 a p-2 b) ∞ ((b q-1 a) r-2 2 b q-2 a(b q-1 a) r-4 2 b q-2 a) ∞ p = 2, q > 2, r > 4 r odd ((ab) r-3 2 ab 2 ) ∞ ((ab q-1 ) r-5 2 ab q-2 ) ∞ r even ((ab) r-4 2 ab 2 ) ∞ ((ab q-1 ) r-4 2 ab q-2 ) ∞ Table
constructions can be recovered from Theorem A. The construction in [START_REF] Dehornoy | Geodesic flow, left-handedness, and templates[END_REF] deals with compact orbifolds, including the case of H 2 /G p,q,r , but the constructed templates have numerous ribbons instead of two here, and the kneading sequences are not determined. Thus, Theorem A is a generalization of the results of [START_REF] Ghys | Knots and dynamics[END_REF][START_REF] Pinsky | Templates for the geodesic flow[END_REF] to compact orbifold of type H 2 /G p,q,r , as well as a simplification of the construction of [START_REF] Dehornoy | Geodesic flow, left-handedness, and templates[END_REF] with more precise information.

The main idea for the proof of Theorem A is to distort all geodesics in H 2 /G p,q,r onto an embedded graph that is just a bouquet of two oriented circles. We perform the distortion in a equivariant way in H 2 (or in fact in T 1 H 2 ), and this allows one to deform through the cone points. We use this freedom to fix a direction in which the deformed geodesic is allowed to wind around a cone point, and this allows us to choose such a simple graph and a template with only two ribbons. In order to have a one-to-one correspondence between orbits of the flow and orbits of the template, the distortion has to obey some constraints. We introduce the notion of spectacles, which allows one to verify that we always get at most one coding for any semi-infinite geodesic and that the coding is nice.

Ultimately we introduce what we call an accurate pairs of spectacles, that ensures we do get some coding for any bi-infinite geodesic. The main intermediate step is the following result which might be of independent interest (see the introduction of Section 3 for the definitions of the graph G p,q,r , of the code, and of the supershift operator σ) Theorem B. Assume that η, ξ in ∂H 2 are the two extremities of a lift in H 2 of a periodic geodesic in H 2 /G p,q,r , then there exists a bi-infinite path γ in G p,q,r that connects η to ξ and whose code w(γ) satisfies u L σk (w(γ)) < u R ( resp. v L σk (w(γ)) < v R ) for every shift σk (w(γ)) that begins with a power of the letter a ( resp. b). This path is unique, except for the paths encoded by the words w L and w R that have the same extremities.

Theorem B is reminiscent of results by Caroline Series [Ser81, Thm 2.7] and Jérôme Los [START_REF] Los | Volume entropy for surface groups via Bowen-Series like maps[END_REF]Thm 4.4]. The novelty here is that we deal with monoids instead of groups, and that we cover some cases that were not addressed by Series (for small values of p, q, and r).

The article is organized as follows. First we recall in Section 2 the topology of the space T 1 H 2 /G p,q,r by giving a surgery presentation on a link in S 3 . We then describe in Section 3 a coding with two letters only for geodesics on H 2 /G p,q,r . In Section 4, we use the coding for constructing a template with two ribbons in T 1 H 2 /G p,q,r and describe its kneading sequences in terms of the chosen coding. We conclude the article with a few questions in Section 5.

In the whole text, p, q, r denote three natural numbers (with r possibly infinite) satisfying 1 p + 1 q + 1 r < 1. We denote by A 0 B 0 C 0 a fixed hyperbolic triangle in H 2 with respective angles π/p, π/q, and π/r. We denote by G p,q,r the orientation-preserving Fuchsian group generated by the rotations of angles 2π/p, 2π/q, and 2π/r around A 0 , B 0 , and C 0 . The quotient H 2 /G p,q,r is then a 2-dimensional orbifold, namely a sphere with three cone points (or a cusp when r is infinite), that we call A ↓ , B ↓ , C ↓ . The letters A and B with sub/superscripts will always denote points of H 2 in the G p,q,r -orbit of A 0 and B 0 respectively.

The topology of T

1 H 2 /G p,q,r
The unit tangent bundle T 1 H 2 /G p,q,r is a Seifert fibered space whose regular fibers correspond to fibers of regular points of H 2 /G p,q,r and exceptional fibers to the fibers of the cone points A ↓ , B ↓ , C ↓ . The goal of this section (Proposition 2.4) is to give a surgery presentation of the 3-manifold T 1 H 2 /G p,q,r with explicit coordinates. This has already been done, for example in [START_REF] José | Classical tesselations and three-manifolds[END_REF]p. 183]. The presentation we give here is slightly different, but more suited to the description of the template T p,q,r . Using Kirby calculus (see [START_REF] Rolfsen | Knots and links[END_REF]p. 267]), one can check that our presentation yields the same manifold as Montesinos'. In this section, the numbers p, q, r can be finite or infinite.

We begin with some elementary lemmas that help us fixing some notation. Assume that γ is an oriented closed curve immersed in a surface. Then the restriction T 1 γ to the fibers of the points of γ of the unit tangent bundle to the surface is a 2-torus which supports four particular homology classes, represented by four vector fields:

1. the fiber f of a given point of γ, oriented trigonometrically, 2. an index 0 vector field z γ ; for example, a vector field that is everywhere tangent to γ, 3. an index +1 vector field u + γ , that is, a vector field that rotates once to the left when traveling along γ, 4. an index -1 vector field u - γ , that is, a vector field that rotates once to the right when traveling along γ.

Lemma 2.1. For γ an embedded oriented curve, the classes [f ] and [z γ ] form a basis of T 1 γ. In this basis, one has

[u - γ ] = -[f ] + [z γ ] and [u + γ ] = [f ] + [z γ ].
Proof. The vector fields f and z γ have exactly one point in common where they intersect transversally, so they form a basis of H 1 (T 1 γ). Rotating along a fiber amounts to turning to the left, so one get [u

+ γ ] = [f ] + [z γ ]. Similarly one obtains [u - γ ] = -[f ] + [z γ ].
Let P be an oriented pair of pants whose three oriented boundary components are denoted by γ A , γ B , γ C . Consider the vector field v on P given by Figure 2

and denote by

v A , v B , v C its respective restrictions to γ A , γ B , γ C . Since v A is tangent to γ A , one has [v A ] = [z A ] on T 1 γ A . Similarly one has [v B ] = [z B ] on T 1 γ B . Now v C is not tangent to γ C .
Since it rotates plus one times when traveling along γ C , one has

[v C ] = [u + C ] on T 1 γ C . γ A γ B γ C Figure 2.
A pair of pants P and the vector field v. The orientations of the boundary components induced by the orientation of P are with larger red arrows.

We denote by C 3 = U A ∪ U B ∪ U C the 3-component link in S 3 that is a chain of 3 unknots, with U C in the middle (see Figure 3).

Lemma 2.2. The unit tangent bundle to the pair of pants P is homeomorphic to S 3 \ C 3 , where the respective meridians of the components U A , U B , U C of C 3 are represented by the vector fields -z A , -z B , f C and the respective longitudes by f A , f B , u + C . Proof. Since P is an open surface, the unit tangent bundle T 1 P is homeomorphic to the product P × S 1 , that is, to S 3 \ C 3 (see Figure 3). The vector field v given by Figure 2 yields a section for this product whose boundary consists of two meridians of U A and U B respectively and one longitude of U C . The respective longitudes of U A , U B and the meridian of U C correspond to three fibers (as can be checked on Figure 3).

The above presentation of T 1 P is not symmetric in the three boundary components. This symmetry can be recovered using a twist. Denote by H 3 + = H A ∪ H B ∪ H C the positive 3-component Hopf link in S 3 (the green link in Figure 1).

U A U B U C f C u + C z C u - C f A u + A z A u - A f B u + B z B u - B Figure 3
. The unit tangent bundle to a pair of pants T 1 P seen as a product P × S 1 , where the section corresponding to the vector field v on P of Figure 2 is shaded. The vector fields f (double arrow, green), z (orange) and u + (purple) for the three boundary tori T 1 γ A , T 1 γ B and T 1 γ C are represented. Next to every torus is represented the homology classes of these vector fields and of u -in the {meridian, longitude}-basis.

Lemma 2.3. The unit tangent bundle to the pair of pants P is homeomorphic to S 3 \ H 3 + , where the respective meridians of the components H A , H B , H C of C 3 are represented by the vector fields -z A , -z B , -z C and the respective longitudes by

u + A , u + B , u + C .
Proof. Starting from the presentation T 1 P S 3 \ C 3 of Lemma 2.2, we perform a positive twist τ C on the component U C , that is, we cut S 3 along a disc bounded by U C and we glue back after performing one full positive turn along this disc (see Figure 4). We denote by H A , H B , H C the images of U A , U B , U C under τ C . The tori H A , H B as well as the fibers of the points of P all get linked plus one times. On these two tori, the twist performs a positive transvection, adding a meridian to the longitude. Since the meridian of U A is represented by the vector field -z A , the meridian of H A is also represented by -z A and the longitude by

f A -(-z A ) = u A + .
The same holds on H B . On the torus U C , the twist performs another transvection, adding a longitude to the meridian. Therefore the longitude of

H C is represented by u C + , as is the longitude of U C . Its meridian is represented by f C -u C + = -z C .
In the above presentation of T 1 P as S 3 \ H 3 + , the fibers of all points of P are fibers of the positive Hopf fibration (see [AGL08] for explanations and movies).

We can now give the desired presentation of T 1 H 2 /G p,q,r . Recall that a Dehn filling with slope a/b on a knot amounts to gluing in a solid torus so that a meridian of the solid torus intersects a longitudes and b meridians of the knot. With this convention, a Dehn filling with slope ∞ amounts to filling the removed knot back in. Here we add the extra-convention that in that case of infinite slope, we keep the knot removed.

H A H B H C f A u + A z A u - A f B u + B z B u - B f C u + C z C u - C Figure 4
. The unit tangent bundle to a pair of pants T 1 P as the complement of a Hopf link. It is obtained from the previous one by a twist along the shaded disc. The vector fields f (double arrow, green), z (orange) and u + (purple) for the three boundary tori T 1 γ A , T 1 γ B and T 1 γ C . On all three tori are represented the homology classes of these vector fields and u -, in the {meridian, longitude}-basis. All meridians are of type -z and all longitudes of type u + .

Proposition 2.4. The 3-manifold T 1 H 2 /G p,q,r can be obtained from S 3 \ H 3 + by Dehn filling the three components of H 3 + with respective slopes p -1, q -1, and r -1. Moreover, the fibers of T 1 H 2 /G p,q,r correspond to the fibers of the Hopf fibration of S 3 \ H 3 + and the exceptional fibers to the cores of the Dehn fillings.

Proof. Since H 2 /G ∞,∞,∞ is a pair of pants, Lemma 2.3 gives the result in this case.

We now suppose p finite (and q, r arbitrary). Let D p be the quotient of a disc D, by a rotation of order p. The orbifold H 2 /G p,q,r is obtained from H 2 /G ∞,q,r by gluing T 1 D p into the cusp γ A (corresponding to the fiber of A ↓ ), formally by first removing a neighbourhood of γ A .

The unit tangent bundle T 1 D p is a solid torus whose meridian disc corresponds to the image on D p of a non-singular vector field on D (see Figure 5). Such a vector field intersects each non singular fiber p times and intersects a vector field tangent to ∂D p once (Figure 5 (d,e)). Therefore after gluing, the meridian of T 1 D p is glued to a curve with coordinates (p -1, ±1) in the {meridian, longitude}-basis of H A . The sign can be fixed either by working out explicitly the action of S 1 as in [START_REF] José | Classical tesselations and three-manifolds[END_REF], or simply by checking that in the p = 1 case the meridian is glued to the curve u + as depicted in Figure 5 (a), hence has coordinates (0, 1). Therefore the gluing corresponds to a Dehn filling of slope p -1.

The cases of q and r are treated similarly.

Note that, if we had not perform the negative Dehn twist in Lemma 2.3, we would obtain the complement of a chain of three unknots instead of the Hopf link, as depicted on Figure 3. In this case, a similar statement to Proposition 2.4 holds by replacing the The fiber T 1 { * } = f * of a point * of ∂D is shown in green, a vector field z ∂D tangent to ∂D in orange and a meridian disc given by a constant vector field in blue. When traveling along ∂D with the orientation induced by the exterior (hence in the clockwise direction), the blue vector field has index +1, that is, it rotates to the left. It is then isotopic to u + ∂D . (b) the action of an order 3 rotation on T 1 D: the vector field z ∂D is invariant, while the meridian disc (in blue) is rotated in the fiber direction, and the fiber f * (in green) is rotated around D. (c) the quotient of T 1 D by an order 3 rotation: a fundamental domain is given by a horizontal slice of the full torus made of those tangent vectors that point between 9 o'clock and 1 o'clock, say. (d) the same picture expanded in the fiber direction. The top and bottom faces are identified using an order 3 rotation. (e) after a twist of -1/3 of a turn, T 1 D 3 is a solid torus with the standard identification of the opposite faces of a cylinder. The meridian disc is still given by the blue vector field. It intersects the fiber of a point (in green) 3 times , and the vector field tangent to ∂D 3 (in orange) minus one times. surgery coeffecients by p, q, and 1-1/r respectively (again, the change of coefficients is coherent with Rolfsen's move [Rol76, p.267]).

Coding of the geodesic flow

The geodesic flow φ on T 1 H 2 H 2 × S 1 is defined in the following way: every unit tangent vector to H 2 is of the form (γ(0), γ(0)) where γ is a geodesic traveled at speed 1, we then set φ t (γ(0), γ(0)) = (γ(t), γ(t)). For G a Fuchsian group, this definition is Gequivariant, and the geodesic flow then projects on T 1 H 2 /G.

These flows are the oldest known example of Anosov flows [START_REF] Anosov | Geodesic flows on closed Riemannian manifolds with negative curvature[END_REF]. Their hyperbolic character implies the existence of a Markov partition [START_REF] Ratner | Markov partitions for Anosov flows on n-dimensional manifolds[END_REF], that is, of a decomposition of the flow into flow boxes whose entry and exit faces glue nicely. However, describing such a coding for explicit groups (for example for surface or triangular groups) is not so easy. This problem has a long history, see among others [MH38, BS79, Ser81, AF91, CN08, Kat08, Pit11] and the references therein.

Here we adapt to our needs the coding given by Caroline Series [START_REF] Series | The infinite word problem and limit sets in Fuchsian groups[END_REF] and completed by Jérôme Los [START_REF] Los | Volume entropy for surface groups via Bowen-Series like maps[END_REF] (who covers some cases that were left out by Series). The main idea in these codings is to distort geodesics in H 2 on a planar Cayley graph of G. Here we do not even need a Cayley graph, but only a planar graph that is G-invariant. In this context, all properties of Series-Los' coding still hold. Our present generalisation works for general Fuchsian groups, but since stating the construction in full generality would make the notations heavier, we only state it in the case we are interested in.

We start with the triangle A 0 B 0 C 0 in H 2 and the group G p,q,r as before. We denote by G p,q,r the embedded graph in H 2 whose vertices are the images of A 0 and B 0 by G p,q,r , and whose edges are the images of the segment (A 0 B 0 ) by G p,q,r (see Figure 6). All vertices of G p,q,r have degree p or q. All components of the complement H 2 \ G p,q,r are polygons with 2r vertices, half of which are in the G p,q,r -orbit of A 0 and half of which in the orbit of B 0 . Definition 3.1 (see Figure 6). Assume that γ := (B 0 , A 1 , B 2 , . . . ) is a semi-infinite path in G p,q,r . The code of γ is the semi-infinite word w(γ) defined as

a k 1 b k 2 a k 3 b k 4 . . . , where +2πk 2i+1 /p (resp. -2πk 2i /q) is the value of the angle B 2i A 2i+1 B 2i+2 (resp. A 2i-1 B 2i A 2i+1 ).
The code of a path starting in the orbit of A 0 is defined similarly, but starts with a power of the letter b. The code of a bi-infinite path (. . . , A -1 , B 0 , A 1 , B 2 , . . . ) is the bi-infinite word . . . a k -1 b k 0 a k 1 b k 2 . . . defined in the same way.

Beware the choice of the opposite orientations for a and b. We denote by lex and < lex the lexicographic ordering on words on the alphabet {a, b}. This choice ensures that the lexicographic ordering on codes and the clockwise ordering on ∂H 2 coincide (Lemma 3.6). Note that two paths obtained one from the other by an element of G p,q,r have the same code. Following an edge corresponds to suppressing the first block of a of b in the code of a path. We then define the super-shift operator σ on infinite words that suppresses, not only the first letter of a word but, the first block of similar letters of a word.

It is easy to see that every geodesic in H 2 is quasi-isometric to a path in G p,q,r , but the latter is not unique. The words u L , u R , v L , v R , w L , w R being given by Table 1 and 2, the goal of this section is to prove Theorem B of the introduction which states that for (almost) every closed geodesic there is a way to choose a unique code.

Pairs of spectacles and admissible paths. Definition 3.2. A base pair of spectacles is a pair of disjoint semi-open intervals {I

A 0 →B 0 , I B 0 →A 0 } in ∂H 2 ,
such that all geodesic rays starting at A 0 and reaching I A 0 →B 0 span an angle 2π/p from A 0 , and all geodesic rays starting at B 0 and reaching I B 0 →A 0 span an angle 2π/q from B 0 . For every oriented edge (A, B) of G p,q,r , the associated spectacle I A→B is the image of I A 0 →B 0 by the unique element of G p,q,r that maps (A 0 , B 0 ) onto (A, B). The spectacles associated to an oriented edge (B, A) is defined similarly.

Remark 3.3. It will usually make sense to choose the base pair of spectacles so that the geodesic rays from A 0 to I A 0 →B 0 include the ray passing through B 0 , and this will be the

A 0 B 0 C 0 I A 0 →B 0 I B 0 →A 0 Figure 6
. The graph G p,q,r in the case p = 3, q = 4, r = 5. In bold is a path through the graph whose code starts with aba 2 b 3 . A choice of a base pair of spectacles P = {I A0→B0 , I B0→A0 } ⊂ ∂H 2 is also depicted.

case for our choice of spectacles in the next section. However, we do not require this in the definition.

Deciding whether the intervals are open on the left or on the right is not important, but in order to avoid heavy case specifications, we arbitrarily decide that all intervals on ∂H 2 are open on the right and closed on the left.

Since I A 0 →B 0 spans an angle 2π/p from A 0 , the p spectacles associated to the p edges starting at a point in the orbit of A 0 tesselate ∂H 2 (and so do the q spectacles associated to the edges starting at a point in the orbit of B 0 ), for any choice of base pair of spectacles. Definition 3.4. Given a base pair of spectacles S, a semi-infinite or bi-infinite path γ in G p,q,r is S-admissible if it has a limit in ∂H 2 , say ξ, and if ξ belongs to all spectacles associated to all oriented edges of γ.

Given a pair of spectacles S and a point ξ on ∂H 2 , it is not clear whether there exists an S-admissible semi-infinite path connecting A 0 (say) to ξ. What is easy to check is that if there is such an admissible path, it is unique. Lemma 3.5. Given a pair of spectacles S, for every A in G p,q,r and every ξ in ∂H 2 , there exists at most one S-admissible path in G p,q,r joining A to ξ.

Proof. The path can be constructed inductively: if the path begins by (A 0 , B 1 , . . . , A 2i ) (resp. (A 0 , B 1 , . . . , B 2i+1 )), there is a unique oriented edge starting at A 2i (resp. B 2i+1 ) whose associated spectacle contains ξ. This gives a unique choice for B 2i+1 (resp. A 2i+2 ). Note that it is not clear that the path so defined converges to ξ.

A nice feature of the coding with two letters given by Definition 3.1 is that the natural cyclic ordering on admissible paths starting at a given point is reflected in the lexicographic order of the codes. Lemma 3.6. Let S be a base pair of spectacles. Assume that γ, γ are two S-admissible paths in G p,q,r that begin with the same edge. Then γ is to the left of γ after they diverge if and only if w(γ) < lex w(γ ) holds.

Proof. The main observation is that, after taking any edge of G p,q,r , the cyclic ordering on the p -1 or q -1 possible next edges coincide with the lexicographic ordering. Indeed, since a corresponds to a rotation of angle + 2π p , a path whose code begins with ab is on the right of a path whose code begins with a 2 b, and so on, and the leftmost paths have codes beginning with a p-1 b. Similarly, since b corresponds to a rotation of angle -2π q , a path whose code begins with ba is on the left of a path whose code begins with b 2 a, and so on. Therefore, two paths coincide as long as their codes coincide. As soon as they diverge, the leftmost has the smallest code.

3.2. Accurate pairs of spectacles and existence of admissible paths. We have seen how a choice of a base pair of spectacles yields a coding for every path in G p,q,r , and leads to the notion of admissible infinite path. Now we want to find spectacles that ensure that every bi-infinite geodesic in H 2 can be shadowed by an admissible bi-infinite path. This is the notion of accurate spectacles. Definition 3.7. A base pair of spectacles S is said to be accurate if for every A in H 2 and for every η, ξ in ∂H 2 there exist an S-admissible semi-infinite path connecting A to ξ and an S-admissible bi-infinite path connecting η to ξ. These paths are denoted by γ S A→ξ and γ S η→ξ respectively. Let us see which codes are yielded by accurate pairs of spectacles. Definition 3.8. Assume that S = {I A 0 →B 0 , I B 0 →A 0 } is an accurate pair of spectacles. Denote by u S L and u S R the respective codes of the admissible paths connecting A 0 to the left and right extremities of I A 0 →B 0 , and by v S L and v S R the codes of admissible the paths connecting B 0 to the two extremities of I B 0 →A 0 . The sequences u S L , u S R , v S L , v S R are called the kneading sequences associated to the pair of spectacles S. Lemma 3.9. Given an accurate pair of spectacles S, a semi-infinite word w = b k 1 a k 2 b k 3 . . . is the code of an S-admissible path if and only if it satisfies u S L lex σ2i+1 (w) < lex u S R and v S L lex σ2i (w) < lex v S R for every i. Proof. Let ξ be a point ∂H 2 . By definition of accurate spectacles, there exists an Sadmissible path γ := (A 0 , B 1 , A 2 , B 3 , . . . ) that connects A 0 to ξ and by Lemma 3.5 this S-admissible path is unique. Denote its code by w. For every i the code of the path (A 2i , B 2i+1 , . . . ) is the word σ2i (w). Since ξ belongs the the interval I A 2i →B 2i+1 , by Lemma 3.6, we have v S L lex σ2i (w) < lex v S R . Similarly, since ξ belongs the the interval I B 2i+1 →A 2i+2 , we have u S L lex σ2i+1 (w) < lex u S R . Conversely, if w satisfies the above constraints, denote the associated path by γ and the limit of γ in ∂H 2 by ξ. Lemma 3.5 implies that ξ belongs to all spectacles I A 2i →B 2i+1 and I B 2i+1 →A 2i+2 . This means exactly that w is S-admissible.

By the same argument, we immediately get Lemma 3.10. Given an accurate pair of spectacles S, a bi-infinite word w = . . . b k -1 a k 0 b k 1 . . . is the code of an S-admissible path if and only if it satisfies u S L lex σ2i+1 (w)

< lex u S R and v S L lex σ2i (w) < lex v S
R for every i. 3.3. An explicit choice of spectacles. Accurate pairs of spectacles yield codes that are easy to describe. However, it is not obvious that there exist accurate pairs of spectacles. For example, if the spectacles I A 0 →B 0 do not include the endpoint of the geodesic ray from A 0 through B 0 , then an admissible path γ S A→ξ would veer away from ξ instead of converging toward ξ. As another example, note that when r is infinite, there exists a unique pair of spectacles. Indeed in this case the graph G p,q,r is a tree, and the only possibility for the intervals I A 0 →B 0 and I B 0 →A 0 is to be the two intervals that connect the extremities of the two horoballs meeting on the edge (A 0 B 0 ).

The goal of this section is to construct explicitly an accurate pair of spectacles in the case where r is finite.

For the rest of this section, assume p > 2. The case p = 2 will be treated in Section 3.5. Assume F is a region of the complement of G p,q,r in H 2 . Since F has 2r vertices, it makes sense to say that two edges are opposite in F : if there are r -1 edges between them in both directions. Definition 3.11 (see Figures 7 and8). Assume that A, B are two adjacent vertices of G p,q,r . Then the associated bigon β AB is defined as the infinite sequence (F 1 , F 2 , . . . ) of faces of the complement of G p,q,r , where F 1 is the face on the left of the edge (AB), the edge F 1 ∩ F 2 is opposite to (AB) in F 1 , and

F i ∩ F i+1 is opposite to F i-1 ∩ F i in F i for every i 2.
The bigon β AB has a left and a right boundary starting at A and B respectively. They both converge to the same point in ∂H 2 that we call the normal extremity of the oriented edge (AB) and denote by ξ AB .

Lemma 3.12. The codes of the paths that follow the left and right boundaries of β AB are the words v R and u L given by Table 1.

ξ A 0 B 0 A 0 B 0 C 0 I f A 0 →B 0 I f B 0 →A 0 Figure 7. The pair of spectacles S f
Proof. We have to draw the corresponding bigon, and to describe its borders. This is depicted in Figure 8. The code is periodic, the period corresponding to one face in the case of r odd and two faces in the case of r even.

Let S f = (I f A 0 →B 0 , I f B 0 →A 0 ) be the pair of spectacles such that the left extremity of I f A 0 →B 0 and the right extremity of I f B 0 →A 0 both coincide with the point ξ A 0 B 0 (see Figure 7). Lemma 3.13. For every A in G p,q,r and ξ on ∂H 2 , the path γ S f A→ξ converges to ξ.

Proof. Let (A 0 , B 1 , A 2 , . . . ) denote the consecutive vertices visited by γ S f A→ξ and b ξ be a Busemann function [START_REF] Busemann | The geometry of geodesics[END_REF] on H 2 associated to ξ . We claim that b ξ is decreasing when evaluated along every second point of

γ S f A→ξ , that is, b ξ (A 0 ) > b ξ (A 2 ) > b ξ (A 4 ) > .
. . holds. Indeed, one checks (see Figure 9) that for every i the spectacles I B 2i+1 →A 2i+2 are included inside the interval of ∂H 2 consisting of those directions that are closer to A 2i+2 than to A 2i .

A B A B a p-1 b a p-1 b 2 a p-1 b a p-1 b a p-2 b a p-1 b a p-1 b 2
2 a p-2 (ba p-1 ) r-2 2 b 2 ) ∞ when r is even (on the right with r = 6). A 0 A 1 A 2 A 3 B 0 I A 0 →B 0 ∩ I B 0 →A 1 I A 0 →B 0 ∩ I B 0 →A 2 I A 0 →B 0 ∩ I B 0 →A 3 ξ A 0 B 0 ξ A 1 B 0 ξ A 2 B 0 ξ A 3 B 0 ξ B 0 A 0 Figure 9.
For every ξ in the interval I A0→B0 ∩ I B0→A1 (approximately the interval between 12:00 and 1:30), the Busemann function b ξ is smaller at A 1 than at A 0 : indeed I A0→B0 ∩ I B0→A1 is included in the half space defined by the perpendicular bisector of (A 0 A 1 ) (dashed) and containing 1 . Similarly for A 2 (1:30 to 3:300) and A 3 (3:30 to 6:00).

Now we have to see why for every η, ξ on ∂H 2 there exists an admissible path that connects η to ξ.

Lemma 3.14. The pair of spectacles S f is accurate.

Proof. We have to show that for every η, ξ on ∂H 2 there exists an S f -admissible path connecting η to ξ. Consider a sequence (A n ) n∈N of points in the orbit of A 0 that converges to η and stays at a bounded distance from the hyperbolic geodesic connecting A 0 to η. By Lemma 3.13 all paths γ S f An→ξ converge to ξ. Also every path γ S f An→ξ is at a bounded distance from the geodesic connecting A n to ξ. Therefore, every path γ S f An→ξ is at a bounded distance from the geodesic that connects η to ξ. Since the orbit of A 0 contains only finitely many points in every ball of bounded radius, this implies that infinitely many paths γ S f An→ξ go through the same point, hence ultimately coincide. By extraction, this yields an S f -admissible path connecting η to ξ.

3.4.

Uniqueness of the coding. The last missing point for proving Theorem B in the case p > 2 is to see when admissible paths fail to be unique. Denote the word (a p-1 b) r-3

2 a p-2 b when r is odd and (a p-1 b) r-2 2 a p-2 b(a p-1 b) r-4
2 a p-2 b when r is even by x L , and the word (b q-1 a) r-3 2 b q-2 a when r is odd and (b q-1 a) r-2 2 b q-2 a(b q-1 a) r-4 2 b q-2 a when r is even by x R . We then have (see Table 2) w L = x ∞ L and w R = x ∞ R . Lemma 3.15. Assume r finite. Suppose that γ 1 , γ 2 are two S f -admissible paths connecting the same points on ∂H 2 . Then either γ 1 , γ 2 coincide in a neighbourhood of ξ in which case their codes are of the form (. . . x L x L x L )w 1 and (. . . x R x R x R )w 2 where w 1 and w 2 are semi-infinite words that ultimately coincide, or γ, γ are disjoint in which case their codes are x ∞ L and x ∞ R . Proof. First suppose that γ 1 , γ 2 have no point in common. Since γ 1 , γ 2 have the same extremities on ∂H 2 , they are separated by an infinite strip of faces of H 2 \ G p,q,r , namely there exists faces . . . , F -1 , F 0 , F 1 , . . . , such that F i+1 is adjacent to F i , that γ 1 is on the left of • • • ∪ F -1 ∪ F 0 ∪ F 1 ∪ . . . and γ 2 on the right. Note that the width of the strip cannot exceed one face. Indeed, since all faces are 2r-gons with r 4 whose vertices have angle at least π/3, one checks that in order to converge to the same point at infinity, one of the paths would have to use more than half of the sides of a face. This would contradict the admissibility of the path: indeed the code of such a path would contain at least r/2 consecutive blocks of the form a p-1 b (or ab q-1 ), and this is prohibited by the kneading sequences of Table 1. Now, for every i, the intersection F i ∩ F i+1 contains two vertices of G p,q,r that we denote by A i and B i . Then γ 1 and γ 2 are two S f -admissible paths connecting B i and A i to ξ. Since γ 1 does not go through A i and γ 2 not through B i , the point ξ belongs to ∂H 2 \ (I A i →B i ∪ I B i →A i ) (the bottom gray interval on Figure 7) for every i. This forces γ 1 ∩ F i ∩ F i+1 to be in the orbit of A for every i and γ 2 ∩ F i ∩ F i+1 to be in the orbit of B.

Assume first r is odd. The previous remark implies that γ 1 and γ 2 both travel along r-1 sides of F i , so that the faces F i-1 and F i+1 are opposite with respect to F i . Therefore, the codes of γ 1 and γ 2 are x ∞ L and x ∞ R . Next, assume r is even. The remark implies that γ 1 and γ 2 travel one along r -2 sides of F i and the other along r sides. Similarly, in the face F i+1 , the two paths travel along r -2 and r sides of F i+1 . If the same path, say γ 1 , travels along r sides of F i and F i+1 , then ξ actually belongs to the interval I A i →B i so that γ 1 should have visited B i , a contradiction. Therefore γ 1 must travel along r sides of F i and r -2 of F i+1 , while γ 2 travels along r -2 sides of F i and r sides of F i+1 . By induction, the codes of γ 1 and γ 2 are x ∞ L and x ∞ R . Now if γ 1 , γ 2 have one point in common, by Lemma 3.5, they coincide after that point. By the same argument as above, the part between them is a semi-infinite chain of 2r-gons. The only possibility for such a chain is to be of the above form.

We can now conclude.

Proof of Theorem B in the case p > 2. We consider the pair of spectacles S f introduced in Section 3.3. By Lemma 3.14 the pair S f is accurate, meaning that for every η, ξ on ∂H 2 , there exists an S f -admissible path connecting η to ξ. By Lemma 3.10, accurate paths are exactly the paths whose code verify the given inequalities. Finally, by Lemma 3.15, if η, ξ are lifts of the extremities of a periodic geodesic this S f -admissible path is unique, except in the case of the words w L and w R .

3.5. Case p = 2. All definitions and lemmas of Section 3.1 and 3.2 and still valid when p = 2. Since faces of H 2 \ G p,q,r now have r sides and not 2r, the definition of bigons (Definition 3.11) and the description of their boundaries (Lemma 3.12) need to be adapted.

We still consider the faces as 2r-gons (with angles at some of the vertices equal to π) and describe the corresponding boundaries. Up to switching between q and r, we can suppose r 5. The kneading sequences in this case are given by Table 1 as shown by Figure 10. 2 ab 2 ) ∞ when r is odd (on the picture with r = 7) and ((ab) r-4 2 ab 2 ) ∞ when r is even. The code v R of the left border is b q-1 ((ab q-1 ) r-5 2 ab q-2 ) ∞ when r is odd and b q-1 ((ab q-1 ) r-4 2 ab q-2 ) ∞ when r is even. The case p = 2, r = 5 on the right: the term (ab q-1 )

b q-1 a b q-1 a b q-2 a b a b a b 2 a b a b b q-1 a b q-2 a b q-2
r-5 2 disappears in v R .
The proofs of Lemmas 3.13 and 3.14 need no special adaptation. Finally the proof of Lemma 3.15 can be translated to this case. The only modification is that for every i the intersection F i ∩ F i+1 consists of two vertices B i 1 and B i 2 that are both adjacent to some point A i , and thus the point ξ belongs to ∂H 2 \(I

A i →B i 1 ∪I A i →B i 2
). If r is odd this forces γ 1 to travel along r-3 2 sides of F i and γ 2 along r-1 2 sides (or r-1 2 and r-3 2 sides respectively). At the next face F i+1 , the same argument as in the proof of Lemma 3.15 proves that the numbers have to alternate. Therefore the codes of γ 1 and γ 2 are those given by Table 2. If r is even the same proof also gives the codes of Table 2.

Finally the proof of Theorem B is now exactly the same that in the case p > 2.

4. The template T p,q,r

We now introduce the main character of this story: the template T p,q,r in T 1 H 2 /G p,q,r . The basic idea is that Theorem B gives a canonical way to distort T 1 H 2 /G p,q,r onto the 2complex that is made of the fibers of the points of G p,q,r /G p,q,r . However, this 2-complex is not a template because it branches along two circles, namely the fibers of the two vertices, instead of along intervals. The trick for proving Theorem A is then to replace the vertices of G p,q,r by roundabouts, thus obtaining a template that has the desired properties. More precisely, we distort any path in G p,q,r in a neighbourhood of each vertex. The crucial point is that since we make the distortion in H 2 , we can choose to push the path to one side of the vertex or the other as we wish. We are therefore able to arrange all paths that pass through a vertex so that they turn around the vertex in a fixed direction (counterclockwise for any image of A 0 , clockwise for any image of B 0 ). Thanks to the admissibility of the original path, the transformed path will rotate by an angle at most p-1 p 2π around A 0 , and at most q-1 q 2π around B 0 . For A, B two adjacent vertices of G p,q,r , we denote by B + the image of B by a +2π/protation around A and by A + the image of A by a -2π/q-rotation around B. Definition 4.1 (see Figure 11). Let B p,q,r be the embedded oriented graph in H 2 /G p,q,r which is a bouquet of two oriented circles, one winding once around A ↓ and one winding minus one times around B ↓ . Let B p,q,r denote the lift of B p,q,r in H 2 . Every lift of a circle is called a roundabout. A switch is the contact point of two adjacent roundabouts. For A, B two adjacent vertices of G p,q,r , we denote by c A B the arc of the roundabout around A that connects the edge (AB) to (AB + ) and by c B A the arc of the roundabout around B that connects the edge (AB) to (A + B).

Every vertex of G p,q,r is canonically associated to a roundabout of B p,q,r , and every edge G p,q,r to a switch of B p,q,r . Definition 4.2 (see Figure 12). Assume that γ = (. . . , A -1 , B 0 , A 1 , . . . ) is a simple path in G p,q,r . The associated tango path ∼ γ is the path in B p,q,r that is obtained by rotating around the roundabouts associated to the vertices of γ and changing at the switches that correspond to the edges of γ.

Define T p,q,r as the branched surface embedded in T 1 H 2 that is made of those vectors of the form (x, v), where x is a point on B p,q,r that belongs to an arc of the form c A B (resp. c B A ) and v is a tangent vector that points into I f B→A (resp. I f A→B ). The surface T p,q,r

A B A + B + A - B - c A B c B A c A B - c B A - Figure 11. The graph B p,q,r .
is a surface made of ribbons of the form c A B × I f B→A (resp. c B A × I f A→B ) that branches in the fibers of the switches of B p,q,r . We equip T p,q,r with a semi-flow, denoted by τ p,q,r , whose orbits are, on every ribbon, of the form c A B × { * } (resp. c B A × { * }). Since we are interested in the topology of orbits and not in the time, the speed is not relevant, we can arbitrarily decide that τ p,q,r travels along each branch at unit speed. In order to say that T p,q,r is a template, we need to check that ribbons are glued nicely.

Lemma 4.3. Every branching arc of the surface T p,q,r is of the form M × I, where M is a switch of the graph B p,q,r and, denoting the vertices of B p,q,r that surround M by A, B, the arc I in ∂H 2 is the segment I f A→B ∪ I f B→A . Proof. In the fiber of M four branches meet, namely c A B , c B A , c A B -, and c B A -. Their visual intervals are respectively I f B→A , I f A→B , I f B -→A , and I f A -→B . Figure 11 shows that all these segments are included in I f A→B ∪ I f B→A .

Lemma 4.3 ensures that T p,q,r is indeed a template: it is made of ribbons, its branching arcs are segments, each branching segment has two incoming ribbons (c A B -× I f B -→A and Figure 12. The broken line represents a bi-infinite path in G p,q,r . The associated tango path in B p,q,r is thickened. All circles correspond to roundabouts.

c B A -× I f A -→B ) that overlap and two outgoing ribbons (c A B × I f B→A and c B A × I f A→B ) that do not overlap. Along the branching segments, the vector fields induced by the different ribbons coincide. By construction, T p,q,r is G p,q,r -equivariant, so we can mod out.

Definition 4.4. The template T p,q,r in T 1 H 2 /G p,q,r is defined as the quotient T p,q,r /G p,q,r . It is equipped with the semi-flow τ p,q,r that is the projection of τ p,q,r .

We can now conclude.

Proof of Theorem A. First we check that T p,q,r is embedded in the way described by Figure 1. Indeed, contracting the ribbons of T p,q,r into arcs bring T p,q,r in a neighbourhood of the vector field v describes on Figure 2, and the arcs c A B , c B A wind once around the corresponding points A ↓ and B ↓ . For the framing of the ribbons of T p,q,r , notice that it is given by the direction of the fibers of T 1 H 2 /G p,q,r . The framing of Figure 1 is obtained by a rotation of 90 degrees, that is, by an isotopy. This proves that the template T p,q,r is indeed embedded as in Figure 1.

Now, all we have to do is to describe a map, say d p,q,r , from T 1 H 2 /G p,q,r to T p,q,r that will transport the orbits of the geodesic flow ϕ p,q,r onto the orbits of the semi-flow τ p,q,r on the template, and check that its restriction to finite collection of periodic orbits is a topological equivalence and an isotopy. Actually, it is easier to do that in a G p,q,r -equivariant way in T 1 H 2 .

Assume that η, ξ are two points in ∂H 2 and denote by g η→ξ the geodesics in H 2 that connects them. By Theorem B, there also exists a unique admissible path γ f η→ξ in G p,q,r that connects η and ξ. We denote it by ∼ γ η→ξ the associated tango path in B p,q,r . The lift of g η→ξ in T 1 H 2 is the orbit g η→ξ × {ξ} of the geodesic flow ϕ p,q,r . We now define d p,q,r as the map that takes g η→ξ × {ξ} onto ∼ γ η→ξ ×{ξ}, which is an orbit of τ p,q,r . Of course, this can be done using an isotopy in the level H 2 × {ξ} and in a G p,q,r -equivariant way. By Theorem B, the image of the map d p,q,r is exactly the template T p,q,r . Modding out the map d p,q,r by G p,q,r , we obtain the desired map d p,q,r .

In order to check that we have an isotopy when we restrict to finite collections of periodic orbits, assume that γ, γ are two arbitrary lifts in T 1 H 2 of two periodic orbits of ϕ p,q,r . Then γ, γ cannot point in the same direction in ∂H 2 , for otherwise they would become arbitrarily close, which is not possible for two periodic orbits. Therefore, the deformation d p,q,r can be realized for these two orbits by two isotopies that live in different levels of T 1 H 2 . These can be extended to a global isotopy of T 1 H 2 . The same idea works for arbitrary (but finitely) many periodic orbits.

Concluding remarks

5.1. Templates with two ribbons. In this article, we have given a construction of a template for some particular geodesic flows. One can wonder about the optimality of the result, that is, whether it can be extended to other geodesic flows on other surfaces or 2-dimensional orbifolds. It was proven in [START_REF] Birman | Knotted periodic orbits in dynamical systems-I: Lorenz's Equations[END_REF] that in this general case, there exists always a template, but with no control on the number of ribbons and the way they are embedded. Explicit constructions were given in [START_REF] Dehornoy | Geodesic flow, left-handedness, and templates[END_REF], but they always yield templates with more than two ribbons. Actually we have Proposition 5.1. Assume that G is a Fuchsian group such that H 2 /G is not a sphere with three cone points. Then there is no template with two ribbons that describes the isotopy classes of all periodic orbits of the geodesic flow on T 1 H 2 /G.

Proof. The set of isotopy classes that can be represented by a template with two ribbons is a submonoid with two generators of π 1 (T 1 H 2 /G). Since the fundamental groups of all Fuchsian groups different from triangles groups have rank larger than 2, they cannot equal a monoid with two generators.

The natural task is then to wonder what are the next simplest templates and which groups they represent. 5.2. Space of codings. In Section 3 we have constructed a particular coding, relying on a particular pair of accurate spectacles. It would be interesting to understand which codings can be obtained in this way.

Question 5.2. Given p, q, r, what is the set of accurate spectacles for coding the periodic geodesics of H 2 /G p,q,r ? More generally, given a generating set of G p,q,r , a coding of periodic geodesics on H 2 /G p,q,r is a language. What we did is to describe one particular such language. Another example is given in [START_REF] Pfeiffer | Automata and Growth Functions for the Triangle Groups[END_REF] (it is not clear to us whether this coding can be obtained using an accurate pair of spectacles).

Question 5.3. Given a generating set of G p,q,r , what is the set of those languages that encode the periodic geodesics of H 2 /G p,q,r ?

Figure 5 .

 5 Figure 5. (a) The unit tangent bundle T 1 D to a disc D is a solid torus D × S 1 .

Figure 8 .

 8 Figure 8. The code u L of the right border of on infinite bigon is the periodic word ((a p-1 b) r-3 2 a p-1 b 2 ) ∞ when r is odd (on the left with r = 5), and ((a p-1 b) r-2

Figure 10 .

 10 Figure 10. An infinite bigon in the case p = 2, r = 7 on the left. The code u L of the right border is the periodic word ((ab) r-3