Marco Cirelli

Emmanuel Moulin

Paolo Panci

Dario Pasquale

Aion Serpico

Viana

Pasquale D Serpico

Aion Viana

Gamma ray constraints on Decaying Dark Matter

come

Introduction

The possibility that Dark Matter (DM), which constitutes most of the matter in the Universe, consists of a particle that actually decays on a very long time scale has attracted much attention lately. This is because the decay time scale τ dec can be taken to be 'short' enough that the decay products give signals in current high energy cosmic ray experiments. Namely, if τ dec few • 10 26 sec, decaying DM can be invoked to explain the excesses in the fluxes of positrons and electrons measured by PAMELA, Fermi and H.E.S.S. [1]. On the other hand, this value of τ dec is so much longer than the age of the Universe that the slow decay does not make a dent in the overall cosmological DM abundance and does not spoil the agreement with a number of astrophysical and cosmological observations [2] 1 .

Irrespectively of this recent activity spurred by the charged CR anomalies, decaying DM is an interesting subject by itself. A long time studied case is the one of supersymmetric gravitino DM [4], which is unstable due to R-parity violation. More generically, in several particle physics models, high-scale suppressed operators may naturally mediate the decay of DM (for a miscellaneous list of references see [5,6,7]).

From the phenomenological point of view, the main feature of decaying DM with respect to the 'more traditional' annihilating DM is that it is less constrained by neutral messenger probes (essentially gamma rays, but also neutrinos) originating from dense DM concentrations such as the galactic center, the galactic halo or nearby galaxies. The reason is simple and well-known: while the signal originating from annihilating DM is proportional to the square of the DM density, for decaying DM the dependence is on the first power; as a consequence, dense DM concentrations shine above the astrophysical backgrounds if annihilation is at play, but remain comparatively dim if DM is decaying. Decaying DM 'wins' instead, generally speaking, when large volumes are considered. This is why in the following we will focus on targets as large as galaxy clusters or, essentially, the whole Universe.

On the observational side, the Fermi and H.E.S.S. telescopes are making unprecedented progress in the field of gamma-ray astronomy, producing measurements of many different targets including those of interest for decaying DM. It is therefore a good time to assess the current status of the latter. To this aim, we will compute the predicted signal from decaying DM, for a variety of decay channels, and compare it to the gamma-ray measurements, deriving constraints on the decay half-life. In particular, in this paper, we make use of two distinct probes:

(I) The isotropic residual gamma ray flux recently measured by Fermi [START_REF] Talk | the TeVPA 2011 conference[END_REF], which now extends from about 200 MeV up to 580 GeV.

(II) The recent observation in gamma rays of the Fornax galaxy cluster by H.E.S.S. [START_REF] Abramowski | [END_REF].

We choose these probes for a number of reasons, besides the obvious fact that they are among the most recent ones. For what concerns the isotropic flux (I), it is known since a long time that it represents a powerful testbed for decaying DM (see for instance [10,11,12]). For what concerns (II), we are again motivated by the fact that large virialized objects such as galaxy clusters are a promising target for decaying DM (as briefly mentioned above) and, more in particular, by the fact that indeed stringent constraints have been recently derived using Fermi data [START_REF] Talk | the FERMI Symposium[END_REF][START_REF] Huang | [END_REF]: on the basis of this we explore the constraining power of a complemetary observatory such as H.E.S.S.. This is particularly interesting because upcoming Čerenkov telescopes offer very promising prospects of improvement in the near future (as opposed to a space based gamma ray observatory such as Fermi, which will at most increase its statistic by a factor of order 1). Indeed, we will also study the sensitivity of CTA, the upcoming large Čerenkov Telescope Array [15].

Incremental improvements to the data and the tools relevant for our analysis also comes from other aspects:

(a) New data on charged Cosmic Rays (CR), which have been recently presented. Fermi [START_REF] Ackermann | The Fermi LAT Collaboration[END_REF] has measured the e + /(e + + e -) fraction, confirming the notorious rise exposed by PAMELA in 2008 [17] and extending the measured spectrum to larger energies (about 200 GeV); Fermi has also presented updated measurements of the total flux of (e + + e -) [18] as well as the measurement of the separated fluxes of e + and of e - [START_REF] Ackermann | The Fermi LAT Collaboration[END_REF]; MAGIC has published [19] the measurement of the total flux of (e + + e -) too; finally, PAMELA has presented results on the flux of pure e -[20], of p [21] and of p [22].

(b) ElectroWeak (EW) corrections to the DM generated fluxes. As discussed in a number of recent works [23], the emission of the EW gauge bosons (W ± , Z) from the SM particles emerging from the DM decay process can significantly modify the phenomenology. (i)

The corrections are particularly relevant for large DM masses (above a TeV); (ii) they can alter significantly the fluxes of charged cosmic rays and gamma rays, both in their spectral shape and in their amplitude, affecting especially the low energies portion [24]. We include EW corrections in all our computations.

(c) An improved propagation scheme for e ± in the Galaxy. In semi-analytic treatments of charged CR propagation in the galactic environment, usually employed in DM studies, the energy losses of e + and e -are generally considered as space-indepedent and their behaviour with energy E is approximated as E 2 . However, a space dependence obviously arises from the different conditions (of magnetic field and of ambient light) in different points of the galaxy and an energy dependence different from E 2 occurs in the full Klein-Nishina regime of Inverse Compton scattering. We make use of the fluxes of e ± as provided in [25], which include these proper space-and energy-dependences. This impacts both the analysis of the e ± fits (mildly) and the fluxes of ICS gamma rays from the galactic halo (more significantly).

Some recent studies have performed work related to ours [26,27,28,29,[START_REF] Zaharijas | for the Fermi-LAT Collaboration[END_REF][START_REF] Ke | [END_REF][START_REF] Talk | the FERMI Symposium[END_REF]32,[START_REF] Huang | [END_REF]. The most closely related, as far as the isotropic gamma ray flux is concerned, is [28], in which a subset of us derived constraints on decaying DM with the data and the tools available at that time. We improve, with respect to that work, by including the updated data in I and by the points (a), (b) and (c) discussed above. There are also some other minor analysis differences on which we will comment in the text. Among other works, ref. [START_REF] Huang | [END_REF] made a particularly detailed analysis: we consider the more recent data in I and II above and we include the Inverse Compton Scattering contribution to the gamma ray flux in the galactic component of I; the points (a), (b) and (c) are new in our paper; we also consider a few more decay channels. For the cases which overlap with this and other studies, we will present a comparison in Sec. 5.1.

The rest of this paper is organized as follows. In Sec. 2 we update charged CR fits by including (a), (b) and (c). In Sec. 3 we discuss the calculation of the constraints from the isotropic residual γ-ray flux, while in Sec. 4 we discuss those from the Fornax cluster. In Sec. 5 we present the combined results. In Sec. 6 we present our conclusions.

Update of the decaying DM fits to charged CR anomalies

As mentioned in Sec. 1, the anomalous PAMELA, Fermi and H.E.S.S. data in e + and (e + +e -) have been interpreted in terms of DM decay. We recall here briefly the main features of the experimental data and of their DM interpretations, without entering in the details of any specific particle physics model.

We use the following data sets:

PAMELA positron fraction [17], selecting only points with E > 20 GeV, in order both to avoid the low energy region affected by the uncertainty of solar modulation and to have a consistent overlap with the Fermi positron fraction data points (the low energy PAMELA data have very small error bars that would overconstrain the fit).

Fermi positron fraction [START_REF] Ackermann | The Fermi LAT Collaboration[END_REF].

Fermi (e + + e -) total flux [18], provided in the low energy (LE) and high energy (HE) samples.

H.E.S.S. (e + + e -) total flux [33,34], also provided in a lower energy portion and a higher energy one.

MAGIC (e + + e -) total flux [19], which however consists of only 6 data points, with error bars larger than those of Fermi and H.E.S.S. at the same energy and therefore has no effect on the global fit.

PAMELA p flux [22].

We perform the fit to these data using the DM generated fluxes as provided in [25], which include the features discussed in points (b) and (c) above. In looking for the best fitting regions, we scan over the propagation parameters of charged cosmic rays and over the uncertainties on the slope and normalization of the astrophysical electron, positron and antiproton background. We have assumed a NFW profile for the galactic DM halo (the specific parameters of which are discussed in Sec. 3), but other choices would have given almost indistinguishable results. We refer to [28] and [35] for more details.

Fig. 1 presents the spectra results for one specific case: the best fit point for the decay mode DM→ µ + µ -. The allowed regions on the plane M DM -τ dec , for the same channel, are instead shown in fig. 2. We show the 95.45 % and 99.999 % C.L. regions for the fit to positron and antiproton data only (green and yellow bands) and for the whole datasets, i.e. including (e + + e -) (red and orange blobs). In fig. 3, which we will discuss in more detail later, we show the global allowed regions for all the channels that we consider.

The typical decay time scales that are required for the global fit are of the order of 10 26 to 10 27 seconds. Moreover, as well known [35], only leptophilic channels allow a global fit: for the quark and gauge boson channels, the few TeV decaying DM needed by (e + + e -) is in conflict with p data.

The impact of the new data and of the improved analysis tools on the identification of the best fit DM properties is overall not big. For instance, in fig. 2 we show the dotted contours of the formerly preferred regions (taken from [28]), which are not very different. However, some features can readily be identified:

-The fit region for the positron and antiproton signals (yellow and green, see fig. 2) starts now at larger masses, due to the fact that Fermi e + data reach higher energies than the former ones from PAMELA.

-An allowed fit region now appears also for the channel DM→ e + e -(see fig. 3); it was not present in previous analyses such as [28]. This is due to a number of concurring reasons, among which the fact that the inclusion of the EW corrections (b) and the refined propagation (c) smoothens out the e + + e -spectrum and allow a decent fit to the ∼ 1 TeV hump, the fact that we now remove from the fit the low energy e + PAMELA datapoints and, also, that we are now employing for Fermi data the full error bars (slightly larger than before).

-EW corrections imply the presence of a non-zero p flux even for leptonic decay channels (see e.g. the third panel of fig. 1). However, the yield is not enough to appreciably affect the fit regions.

A comment on the selection of the datasets and their compatibility is also in order. We use the full set of data listed at the beginning of this section, but we also checked that dropping the data by PAMELA on the positron fraction, i.e. using only data from Fermi and H.E.S.S.

(on the positron fraction and the pure e + and e -fluxes), does not significantly change the fit regions. Similarly, the regions are not significantly modified if we adopt for the positron astrophysical background the recent determination in [36] (instead of the one conventionally used, from [37,38]). This is expected, since the predictions in [36] and in [37,38] are very similar in the range of energies in which we are interested.

Isotropic gamma ray flux

The measurements in (I) by the Fermi satellite correspond to the (maximal) residual, isotropic gamma-ray flux present in their data. Its origin can be in a variety of different phenomena, both in the form of unresolved sources and in the form of truly diffuse processes (see [START_REF] Talk | the TeVPA 2011 conference[END_REF] and reference therein). DM decays can also contribute to this isotropic flux, with two terms: 1) an extragalactic cosmological flux, due to the decays at all past redshifts; 2) the residual emission from the DM halo of our Galaxy. The former is of course truly isotropic, at least as long as one neglects possible nearby DM overdensities. The latter is not, but its minimum constitutes an irreducible contribution to the isotropic flux. In formulae, the predicted differential DM flux that we compare with Fermi isotropic diffuse γ-ray data is therefore given by

dΦ isotropic dE γ = dΦ ExGal dE γ + 4π dΦ Gal dE γ dΩ minimum (1)
For typical DM decay channels and for any DM halo profile, we find that the two contributions are of comparable amplitude, as it can be seen e.g. in the lower right panel of fig. 1. We now move to discuss the calculations of the two contributions separately, reproducing and updating the discussion of [28].

The extragalactic flux is given, in terms of the Earth-measured photon energy E γ , by

dΦ ExGal dE γ = Γ dec Ω DM ρ c,0 M DM ∞ 0 dz e -τ (Eγ (z),z) H(z) dN dE γ (E γ (z), z) , (2)
where Γ dec = τ -1 dec is the decay rate. Here the Hubble function

H(z) = H 0 Ω M (1 + z) 3 + Ω Λ
, where H 0 is the present Hubble expansion rate. Ω DM , Ω M and Ω Λ are respectively the dark matter, matter and cosmological constant energy density in units of the critical density, ρ c,0 . The gamma ray spectrum dN/dE γ , at any redshift z, is the sum of two components: (i) the high energy contribution due to the prompt γ-ray emission from DM decays and (ii) the lower energy contribution due to Inverse Compton Scatterings (ICS) on CMB photons of the e + and e -from those same decays. Using eq. ( 2), the extragalactic flux can therefore be computed in terms of known quantities for any specified DM mass M DM and decay channel. In particular, since the flux essentially consists of the integral over ρ, at the first power, the result is not affected by the formation of DM halos, the history and the properties of which are highly uncertain. This is in contrast to the case of annihilating DM, where instead these issues affect the predictions by orders of magnitude (see e.g. [39,40]). We take the resulting fluxes from [25], but we improve the treatment of the effect of the finite optical depth of the Universe, as we now move to discuss.

The factor e -τ (Eγ ,z) in eq. ( 2) accounts for the absorption of high energy gamma rays due to scattering with the extragalactic UV background light: essentially, a high energy photon from DM hits a lower energy UV photon and produces an energetic electron (or positron) which, in turn, makes Inverse Compton Scattering on the CMB and therefore reinjects a continuum of lower energy γ-rays. The process amount to a subtraction of γ-ray flux from the higher energies and a redistribution towards the lower part of the spectrum. As an element of novelty in this analysis, we take this process fully into account, using the energy and redshift dependent optical depth of the Universe (denoted τ (E γ , z)) of [25]. The effect is sizable at energies E γ 100 GeV: it can reduce the high energy flux by about one order of magnitude. Indeed, in fig. 1, lower right panel, we show with dotted lines the fluxes computed neglecting absorption and with dashed lines the effect of including it. Summing over the galactic component (which is of course not affected by absorption) reduces the impact of the effect, which can however remain sizable. This will affect the constraints derived below, especially for channels which feature a large prompt contribution.

The flux from the galactic halo, coming from a generic direction dΩ, is given by the well known expression

dΦ Gal dE γ dΩ = 1 4π Γ dec M DM los ds ρ halo [r(s, ψ)] dN dE γ , (3)
i.e. as the integral of the decaying DM density piling up along the line of sight individuated by the direction dΩ. Here ρ halo is the DM distribution in the Milky Way, for which we will always take a standard Navarro-Frenk-White [41] profile

ρ NFW (r) = ρ s r s r 1 + r r s -2 , (4)
with parameters r s = 24.42 kpc and ρ s = 0.184 GeV/cm 3 [25]. In principle one could consider other choices of profiles and parameters, but, for the case of decaying DM and considering that we will not be interested in the regions of the Galactic Center (GC) where profiles differ most (quite the opposite: we will focus on the anti-GC), these choices make a negligible difference. The coordinate r, centered on the GC, reads r(s, ψ) = (r 2 + s 2 -2 r s cos ψ) 1/2 , where r = 8.33 kpc is the most likely distance of the Sun to the GC and ψ is the angle between the direction of observation in the sky and the GC. The spectrum dN/dE γ consists again of two components: the prompt one and the ICS one. We compute both using the tools in [25]. In particular, for the ICS flux we use the generalized halo functions for the IC radiative process provided there, which take into account the full energy losses discussed in (c). This is another refinement with respect to [28], which had computed the e ± energy losses towards the anti-GC including CMB only: it was thus missing synchrotron losses (which can account for up to roughly a third of the total losses, in the range 8.33 kpc r 15 kpc) and ICS losses on local ambient light other than the CMB (which are instead less important). The treatment that we now adopt represents the most refined one we can afford, at the current state-of-the-art of these semi-analytical computations.

As indicated in eq. ( 1) and in the discussion above it, we need to determine the minimum of the flux in eq. (3). For the prompt contribution, the minimum is obviously located where the line-of-sight density of DM is the lowest, just because the γ-ray emission density traces the DM density by definition. This coincides with the direction of the anti Galactic Center (anti-GC). For what concerns the ICS contribution, on the other hand, the situation is more complicated. In this case the source of γ-rays is the population of DM-originated e ± , and therefore the minimum depends on what is assumed for the propagation and final distribution of the latter ones in the galactic halo. For instance, assuming a thin diffusive halo with L = 1 kpc (see e.g. [25] for a discussion and an overview of standard values) implies that the layer of ICS emitting e ± is particularly shallow in the zenith (and nadir) direction and therefore the ICS γ-ray flux is minimal along lines of sight pointing directly above (and below) the solar system. On the other hand, for a thick L = 15 kpc diffusive halo, the ICS emission from the directions orthogonal to the galactic plane is greatly enhanced and the minimum is located again at the anti-GC. In view of this complicated morphology, we choose to locate the minimum always at the anti-GC:

dΦ Gal d dΩ minimum -→ dΦ Gal d dΩ anti-GC (5)
This is supported, along the lines of the discussion above, by a number of considerations, among which: (i) thin diffusive halos are anyhow disfavored by other arguments (see e.g. [42]); (ii) a number of other uncertain astrophysical variables would enter in a detailed determination of a true minimum: for instance if the radial size of the diffusive halo is smaller than usually assumed (∼20 kpc), then the ICS flux at the anti-GC is reduced; (iii) this discussion only affects the galactic ICS contribution (not the galactic prompt and the extragalactic contributions), thus limiting the impact on the derived total flux and having an importance (for the bounds we will derive below) only for those configurations in which the ICS saturates the constraints.

Deriving the constraints

We thus compute dΦ isotropic /dE γ as discussed above and we compare it with the Fermi data of (I). We show an example of such a comparison in Fig. 1, lower right panel. It is pretty clear (even by inspection, in the case of this example) that the DM signal does not agree in shape with the data, which are instead well fit by a simple power law [START_REF] Talk | the TeVPA 2011 conference[END_REF]. For this reason, we are driven to derive constraints on the maximum DM signal, and therefore the minimum τ dec , admitted by the data. There are however several possible ways to compute such constraints. We discuss a few of them in the following and we illustrate them in the specific example of fig. 2.

• DM signal only. The most conservative option consists in demanding that the DM signal alone (eq. ( 1)) does not exceed any single one of the Fermi data points by more than a chosen significance, which we set at 3σ. This is overly conservative for a number of reasons. First of all, since it supposes a vanishingly small astrophysical background. A simple inspection of the DM prediction proves that this assumption is physically untenable; the bumpy shape of the signal is so different from the featurless observations that the (bulk of the) latter must be explained by astrophysical processes, leaving only a subleading role for signals from DM. Second, given the smooth nature of the DM signal and of the data, it is clear that an excess of 3σ in one point is often accompanyed by similar excesses in neighboring points, so that the 'global significance' of the exclusion is actually higher. For instance, the best-fit model example in fig. 1 is only barely excluded by such a procedure, despite the clear tension with several data points.

• DM signal + power-law background. A more realistic option consists in assuming that the astrophysical background consists of a power-law and demand that the sum of astrophysical background and DM signal does not exceed a chosen global significance. A power-law background for the extragalactic flux, indeed, is justified by a variety of suspected sources such as unresolved blazars, radio-loud galaxies or star-forming galaxies. More precisely, we find that the data of E 2 γ dΦ/dE γ dΩ alone are very well described by a power law with index -0.41 and normalization 1.02 10 -5 GeV/(cm 2 sec sr). Next, for a given M DM we add the DM signal, whose normalization is controlled by Γ dec . We let the normalization of the power law background vary within a factor of 2 from the central value specified above and its index within 0 and -1 (this choice is astrophysically plausible, although varying the parameters in a broader range would not change the results shown). We then compute the χ 2 to the data, marginalizing over these parameters. We compute in this way 95% C.L. limits on Γ dec .

• DM signal + unconstrained background. A variation of the procedure described in the previous point consists in avoiding to commit on the functional form of the background and assume that it consists of an arbitrary function which describes well the data (namely: it is consistent with each data point within a small significance, e.g. 1σ).

We then demand that, adding the signal, the ∆χ 2 does not exceed a given value, which in this case we fix very conservatively at 25. For the practical case at hand, however, this procedure and the previous one yield similar results, as one can see on the example in fig. 2. This is not surprising, since the isotropic residual datapoints are indeed very well described by a power law.

The procedure 'DM signal + power-law background' is the one that we will adopt to obtain the fiducial constraints shown in our results (see fig. 3). This procedure is 'fiducial' also in the sense that it matches the analysis we do for charged CR anomalies (see Sec. 2) and therefore fit regions and constraints are essentially consistent with each other in fig. 3.

Fornax cluster gamma ray flux

Galaxy clusters are the largest gravitationally bound structures in the universe, 80% of their total mass being in the form of Dark Matter. Although they are located at much larger distances than other popular targets such as dwarf satellites of the Milky Way, they turn out to be attractive environments to search for DM due to their predicted high DM luminosity. In practice, which cluster is the most promising depends on a number of factors, and most notably the astrophysical background. Indeed, standard astrophysical gammaray emission is expected, both from high energy cosmic rays interacting in the intra cluster medium (the dominant contribution) or from electrons in the ambient radiation field (a subdominant contribution, see [43] for a review). Despite these predictions, no gamma-ray from these processes has been detected so far [44,45,46,47,[START_REF] Ackermann | Fermi-LAT Collaboration[END_REF][START_REF] Abramowski | [END_REF]. Radio galaxies lying at the gravity center of clusters such as M87 in Virgo and NGC1275 in Perseus are also γ-ray emitters: these have actually been directly observed.

A few galaxy clusters have been observed by H.E.S.S.: the most attractive of them for DM searches are Virgo, Coma and Fornax. Although Virgo is closeby, the high energy gamma-ray emission from M87 prevents searches in the inner region. Coma is among the most massive galaxy clusters but it has been shown that it is not a privileged environment because of a relatively high CR-induced gamma-ray emission [51,52]. Fornax is located at 19 Mpc [49] and shows favorably-low expected astrophysical background (see, for instance, [50,51,52]). Given its location near the tropic of Capricorn, the H.E.S.S. instrument is bestsuited to observe Fornax with respect to other currently-operating Imaging Atmospheric Čerenkov Telescopes (IACTs).

The predicted DM γ-ray flux from Fornax can be easily obtained by integrating Eq.( 3) over the observational solid angle ∆Ω, and of course replacing ρ halo with ρ Fornax , the DM distribution in the cluster.

There are a few different methods to determine ρ Fornax (and in general the DM content of galaxy clusters). A widely used approach is based on X-ray measurements on the gravitationally bound hot intracluster gas. Assuming a NFW profile [41], the latter is entirely defined from the virial mass extracted form the HIFLUGCS catalog catalog [49] and the virial mass and the concentration relationship found in Ref. [53], in ΛCDM cosmology. Other choices for the profile are possible, e.g. the cored Burkert profile [54], which may be particularly motivated by the fact that baryon physics in the inner part of clusters may significantly alter the predictions of ΛCDM simulations: several processes invoking baryons in galaxy formation such as dynamical friction, AGN feedback or gas outflows, may flatten the DM cusps in DM cores [55,56]. For the case of Fornax, various dark matter halo models have been considered in [START_REF] Abramowski | [END_REF] (and references therein). However, as opposed to the annihilation case, the gamma-ray flux from decaying DM is less dependent on the DM distribution inside the target due to the simple linear dependence of the astrophysical factor with DM density. Varying over the profiles discussed in [START_REF] Abramowski | [END_REF], the difference in the flux factor is less than a factor of 3 for a given opening integration angle. Another approach to determine the DM content of clusters consists in using dynamical tracers (see again [START_REF] Abramowski | [END_REF] and references therein).

In the following, we take as 'fiducial' the X-ray based determination of the DM profile, hereafter referred to as the RB02 profile [START_REF] Abramowski | [END_REF], which also well agrees with tracer dynamics at large distances. In this case, the DM distribution is inferred from a X-ray concentrationvirial mass relationship2 and the uncertainty on the mass determination is about 10% [53]. As an alternative choice, we also consider the DW01 profile of [START_REF] Abramowski | [END_REF], which is fully based on the dynamical tracers method. This generates a predicted DM γ-ray flux ∼3 times smaller than RB02.

Next, we discuss the choice of ∆Ω. In contrast to annihilating dark matter for which most often the smallest opening angle provide the most sensitive searches, at least for cuspy profiles, decaying dark matter searches require optimization of the opening angle to guarantee the highest signal-to-noise ratio. As it is straightforward from Eq.( 3), the luminosity scales with the size of the solid integration angle. On the other hand, background is increasing as well. We find that the optimization of the signal-to-noise ratio versus the opening integration angle for the dark matter halo profile RB02 implies the best integration region to be 0.5 • , which corresponds to a solid angle of ∆Ω = 2.4 × 10 -4 sr.

We also mention that an additional component to the decaying Dark Matter spectrum needs in principle to be considered, particularly for leptonic final states: that of Inverse Compton emission (indeed, as opposed to dwarf galaxies, in clusters the electrons lose energy primarily through ICS on the ambient radiation field and produce additional gamma rays in the final state). We include it in the computations for the DM → µ + µ -channel, but, due to the energy working range of H.E.S.S., this component becomes important only for very large DM masses (above ∼ 30 TeV) and its effect is therefore not visible in our results.

Deriving the constraints

In order to extract exclusion limits on the Dark Matter lifetime from gamma-ray astronomical observation with IACTs, the background needs to be determined to constrain the decaying DM luminosity. The background is calculated in a region referred to as the OFF region, and the signal region as the ON region. Both ON and OFF regions depend on the observation mode and are specific to the IACT instrument. As for the background level, it is taken simultaneously, i.e. in the same data-taking observing conditions, to the signal events in order to allow for the most accurate estimate.

In the 'standard' ON-OFF method, one has to take into account the background flux in the astrophysical factor and subsequently in the upper limit calculation. For the ON region of 0.5 • and considering a OFF region in an annulus around the ON region with an inner and outer radii of 0.5 • and 1.0 • respectively, this reduces the decaying DM flux in the ON region of about 40%. An 'improved' background estimate procedure called the template method allows to avoid this reduction. In such method the background events are determined in the ON region but from selecting hadron-like events (see [START_REF] Abramowski | [END_REF] for details on the analysis procedure). We indeed make use of it in this work.

H.E.S.S. has observed Fornax for a total of 14.5 hours at low zenith angle to allow for best sensitivity to low dark matter masses.

Results and discussion

Figure 3 presents the exclusion plots and therefore summarizes our main results. One can see that the constraints from the Fermi isotropic γ-ray data exclude decaying DM with a lifetime shorter than 10 26 to few ×10 27 seconds, depending on its mass and the precise channel. Therefore, in particular, they rule out the charged CR fit regions, for all the channels. As illustrated in the example in fig. 2, and inspecting fig. 1, adopting the more conservative constraint procedure may marginally reallow a portion of the fit regions, for the DM → µ + µ -, but leaving a clear tension. The constraints from Fermi rise gently as a function of the mass, essentially as a consequence of the fact that the measured flux rapidly decreases with energy. They also depend (mildly, a factor of a few at most) on the decay channel, as a consequence of the different γ-ray yield and the different shape of the DM signal in each channel.

The constraints from H.E.S.S. Fornax remain subdominant, roughly one order of magnitude below the Fermi ones. However, for the case of the DM → τ + τ -channel, the bound also reaches the CR fit region and essentially confirms the exclusion. The constraints are cut at low masses by the dying out of the sensitivity in H.E.S.S. to low energy photons. They do not look competitive with respect to Fermi even for larger masses.

In this study we have focussed on 2-body particle-antiparticle decay modes (DM → + -, q q, W + W -, where is a charged lepton), typical of scalar DM. We do not address 3-body decays such as DM → + -γ, since those are model dependent. For fermionic DM, decay channels such as DM → ± W ∓ are possible: these (in first approximation) can be analysed in our framework with a trivial combination of the DM → + -and DM → W + W - channels. Another possibility which has been recently considered is mixed ('democratic') leptonic channels, such as DM → 33% e + e -+ 33% µ + µ -+ 33% τ + τ -: these can of course simply derived on the basis of our individual bounds.

Comparison with existing bounds

We here comment on the relative strength of the constraints in fig. 3 with respect to bounds from other analyses or other targets. With respect to the isotropic γ-ray constraints of [28], the bounds derived here are stronger by a factor of 2 to 3. The reasons of this are discussed at length in the text and essentially amount to: updated datasets, more refined DM analyses and the adoption of a more realistic constraint procedure (some of these effects pull towards a weakening while others for a strengthening).

With respect to the work in [START_REF] Huang | [END_REF], our constraints from the Fermi isotropic background are somewhat stronger than their corresponding ones (up to about a factor of 5 for the DM → µ + µ -channel), likely due to the several differences in the analysis discussed in Sec. 1. In addition, [START_REF] Huang | [END_REF] presents bounds from the observation of the the Fornax cluster by Fermi: these are less stringent than our Fermi isotropic background constraints but more powerful than our H.E.S.S.-based constraints at moderate masses. At the largest masses, our H.E.S.S.-based constraints pick up and match theirs (for the bb channel), as expected from the different operational energy range of Fermi versus H.E.S.S.. The bounds from clusters other than Fornax are less powerful, according to the analysis in [START_REF] Huang | [END_REF]. Ref. [58] has derived constraints from several clusters using Fermi data too, but their procedure is questioned in [START_REF] Huang | [END_REF], and in any case it is now superseded. On the other hand, the preliminary constraints shown (for the bb channel only) in [START_REF] Talk | the FERMI Symposium[END_REF], obtained with a combination of several clusters in Fermi, exceed our bounds by a factor of 2.

Bounds from probes other than the isotropic flux and clusters do not generally achieve the same constraining power. E.g. recently [59] finds less stringent limits for the leptophilic channels, focussing on the Milky Way halo.

Within the context of observations performed by IACT, we note that the decay lifetime constraints obtained with galaxy clusters are stronger than those from dwarf galaxies. Even for the ultra-faint dwark galaxy Segue 1, which is believed to be the most attractive dwarf in the northern hemisphere3 , the constraints are 2 orders of magnitude higher for a dark matter particle mass of 1 TeV [60].

We also estimate that the constraints that we derive are stronger than those that can come from neutrino observation of the Galactic Center (see for instance [61]). Precisely computing those ones for all channels and in the same analysis framework of this study, however, is beyond the scope of this work, and would also probably benefit from a better knowledge of the Icecube data (especially the reconstructed neutrino energy), which is not currently available. In summary: with the possible exception of the preliminary bounds from a combination of clusters by Fermi for the b b channel, the constraints that we derive from the isotropic γ-ray flux are the most stringent to date.

Prospects for improvements

As we have seen, currently the constraints on decaying DM from the Fermi satellite are dominant with respect to those from H.E.S.S.. However, while the former may increase its statistics by at most a factor of a few, for the latter there are prospects of developments in the mid-term future.

The next-generation IACT will be a large array composed of a few tens to a hundred telescopes located on two sites, one in each hemisphere [62]. The goal is to improve the overall performances of the present generation: one order-of-magnitude increase in sensitivity and enlarge the accessible energy range both towards the lower and higher energies allowing for an energy threshold down to a few tens of GeV. From the actual design study of CTA, the effective area will be increased by a factor 10 and a factor 2 better in the hadron rejection is expected.

The calculation of the CTA sensitivity follows the methodology described in [63] and adapted to the case of decaying Dark Matter. The effective area and the background estimate are extracted from Ref. [63]. The limit on the number of gamma-ray events is calculated assuming the background-only hypothesis and the sensitivity on the decay lifetime is computed at 95% C.L.

Figure 3 shows the 95% C.L. sensitivity of CTA on the decay lifetime for the RB02 halo profile for 50h observation time and ∆Ω = 2.4 × 10 -4 sr.

To conclude, we also mention that a technique which could allow for significant improvements in the exploration of the parameter space of decaying DM using clusters is the one of stacking the observation of a large number of different clusters, as recently discussed in [64]. The authors find that improvements of up to 100 can be theoretically achieved, albeit this factor is ∼5 for more realistic background-limited instruments.

Conclusions

Decaying Dark Matter has come to the front stage recently as an explanation, alternative to annihilating DM, for the anomalies in CR cosmic rays in PAMELA, Fermi and H.E.S.S.. But, more generally, decaying DM is a viable possibility that is or can naturally be embedded in many DM models. It is therefore interesting to explore its parameter space in the light of the recent observational results.

We discussed the constraints which originate from the measurement of the isotropic γ-ray background by Fermi and of the Fornax cluster by H.E.S.S., for a number of decaying channels and over a range of DM masses from 100 GeV to 30 TeV. We improved the analysis over previous work by using more recent data and updated computational tools.

We found (see fig. 3) that the constraints by Fermi rule out decaying half-lives of the order of 10 26 to few 10 27 seconds. These therefore exclude the decaying DM interpretation of the charged CR anomalies, for all channels, at least adopting our fiducial constraint procedure. The constraints by H.E.S.S. are generally subdominant. For the DM → τ + τ -channel, they can however also probe the CR fit regions and essentially confirm the exclusion.

With one possible exception for the DM → b b channel, the constraints that we derive from the isotropic γ-ray flux are the most stringent to date.

We also discussed the prospects for the future Čerenkov telescope CTA, which will be able to probe an even larger portion of the parameter space.

  Photon Energy E Γ GeV

Figure 1 :

 1 Figure 1: An example of the signals in different channels from a decaying DM candidate that fits the charged CR anomalies: we show the positron fraction (upper left), all leptons (upper right), antiproton (lower left) and isotropic gamma ray (lower right) spectra for the best fit candidate DM → µ + µ -, namely M DM = 3760 GeV, τ dec = 1.6 10 26 sec (marked by a white cross in fig.s 2 and 3). The ' PAMELA 2008' datapoints are reported for completeness, but we use only the more recent ' PAMELA 2010' in the fits (see text for details). In each panel, the DM contributions are dashed and the astrophysical background is shaded gray. In the lower right panel, the dotted (dashed) lines refer to the flux neglecting (including) extragalactic absorption, see Sec. 3.

Figure 2 :

 2 Figure 2:Illustrative example (for the channel DM→ µ + µ -) of the impact on the fit and constrained regions following from different assumptions and choices, as discussed in the text. In fig.3, on the other hand, we will show only the final regions and our fiducial constraints.

Figure 3 :

 3 Figure3: The regions on the parameter space M DM -τ dec that are excluded by the Fermi and H.E.S.S. constraints and that can be explored by CTA, together with the regions of the global fit to the charged CR data, for different decay channels.12

See instead[3] for cases in which the decay of DM may actually help cosmology or astrophysics, but for much shorter decay time scales, excluded by the bounds we will present below.

The virial galaxy cluster mass M ∆ is usually defined as the enclosed mass within a radius where the density reaches ∆ × ρ c , with ρ c the critical density of the universe and ∆ taking values between 100 and 500. Although M 500 can be used to derive specific galaxy cluster properties, the X-ray concentration-mass relation is particularly well verified for ∆ = 200[57].

Ultra-faint dwarf galaxies are particularly interesting due to their high mass-to-light ratio. However the nature of some of them is still under debate due to their similarity of their properties with globular clusters. Due to their low surface brightness and a few tens of member stars, their dark matter content is still subject to large uncertainties.

Acknowledgements We thank Daniela Borla Tridon for communications on MAGIC data, Carlos de los Heros for communications on Icecube data and Alejandro Ibarra for useful discussions. This work is supported by the French National Research Agency ANR under contract ANR 2010 BLANC 041301 and by the EU ITN network UNILHC. PS thanks CERN's Theory Division for hospitality during the development of this work.


T Accadia

F Acernese

F Antonucci

P Astone

G Ballardin

F Barone

M Barsuglia

A Basti

Th S Bauer

M Bebronne

M G Beker

A Belletoile

S Birindelli

M Bitossi

M A Bizouard

M Blom

F Bondu

L Bonelli

R Bonnand

V Boschi

L Bosi

B Bouhou

S Braccini

C Bradaschia

M Branchesi

T Briant

A Brillet

V Brisson

R Budzyński

T Bulik

H J Bulten

D Buskulic

C Buy

G Cagnoli

E Calloni

B Canuel

F Carbognani

F Cavalier

R Cavalieri

G Cella

E Cesarini

O Chaibi

E Chassande-Mottin

A Chincarini

F Cleva

E Coccia

P.-F Cohadon

C N Colacino

J Colas

A Colla

M Colombini

A Corsi

J.-P Coulon

E Cuoco

S D'antonio

V Dattilo

M Davier

R Day

R De Rosa

G Debreczeni

W Del Pozzo

M Del Prete

L Di Fiore

A Di Lieto

M Di

Paolo Emilio

A Di Virgilio

A Dietz

M Drago

V Fafone

I Ferrante

F Fidecaro

I Fiori

R Flaminio

L A Forte

J.-D Fournier

J Franc

S Frasca

F Frasconi

M Galimberti

L Gammaitoni

F Garufi

M E Gáspár

G Gemme

E Genin

A Gennai

A Giazotto

R Gouaty

M Granata

C Greverie

G M Guidi

J.-F Hayau

A Heidmann

H Heitmann

P Hello

D Huet

P Jaranowski

I Kowalska

A Królak
email: krolak@impan.gov.pl

N Leroy

N Letendre

T G F Li

N Liguori

M Lorenzini

V Loriette

G Losurdo

E Majorana

I Maksimovic

N Man

M Mantovani

F Marchesoni

F Marion

J Marque

F Martelli

A Masserot

C Michel

L Milano

Y Minenkov

M Mohan

N Morgado

A Morgia

S Mosca

V Moscatelli

B Mours

F Nocera

G Pagliaroli

L Palladino

C Palomba

F Paoletti

M Parisi

A Pasqualetti

R Passaquieti

D Passuello

G Persichetti

M Pichot

F Piergiovanni

M Pietka

L Pinard

R Poggiani

M Prato

G A Prodi

M Punturo

P Puppo

D S Rabeling

I Rácz

P Rapagnani

V Re

T Regimbau

F Ricci

F Robinet

A Rocchi

L Rolland

R Romano

D Rosińska

P Ruggi

B Sassolas

D Sentenac

L Sperandio

R Sturani

B Swinkels

M Tacca

L Taffarello

A Toncelli

M Tonelli

O Torre

E Tournefier

F Travasso

G Vajente

J F J Van Den Brand

C Van Den Broeck

S Van Der Putten

M Vasuth

M Vavoulidis

G Vedovato

D Verkindt

F Vetrano

A Viceré

J.-Y Vinet

S Vitale

H Vocca

R L Ward

M Was

M Yvert

J.-P Zendri

Status of the Virgo project

We describe the present state and future evolution of the Virgo gravitational wave detector, realized by the Virgo Collaboration at the European Gravitational Observatory, in Cascina near Pisa in Italy. We summarize basic principles of the operation and the design features of the Virgo detector. We present the sensitivity evolution due to a series of intermediate upgrades called Virgo+ which is being completed this year and includes new monolithic suspensions. We describe the present scientific potential of the detector. Finally we discuss the plans for the second generation of the detector, called Advanced Virgo, introducing its new features, the expected sensitivity evolution and the scientific potential.

Introduction

The first generation of km-scale interferometric gravitational-wave detectors Virgo [1], LIGO [2] and GEO600 [3] are engaged in a search for gravitational-waves from astronomical sources. These projects form an international collaboration that analyzes jointly the data from all the detectors. Gravitational waves have not been detected yet, but searches for sources like binary systems of neutron stars and/or black holes, energetic bursts, rotating isolated neutron stars and a gravitational wave background from the early universe have led to upper limits (see Section 6 for more details). These upper limits are beginning to provide an important astrophysical information about the Universe and thereby opening a new observational field -the gravitational wave astronomy. In this paper we shall review the current status of one of the gravitationalwave detectors -the Virgo project.

Virgo project

Virgo is the gravitational wave detector funded by CNRS (France) and INFN (Italy). Its construction was completed in June 2006. Virgo is a recycled Michelson interferometer with 3 km-long Fabry-Perot cavities in its arms. Virgo is located at the European Gravitational Observatory (EGO), close to Cascina (Pisa, Italy). It is the only ground-based antenna that, from its conception, aimed at reducing the detection band lower threshold down to 10 Hz. This goal has been achieved by isolating the interferometer mirrors from seismic noise which, in the tens of Hz range, is many orders of magnitude larger than the small variation of the arm length induced by the gravitational wave passage. In recent years other European research groups (from Holland, Poland, Hungary, and UK) have joined the collaboration. An aerial view of the Virgo detector is shown in Figure 1.

Virgo detector

In Figure 2 we present diagram of the optical design of the Virgo detector. The laser beam, after passing through the optical table for its alignment, enters the vacuum system, reaching the input optical bench (IB). The beam is then spatially filtered by a 144 m-long triangular cavity (input mode cleaner -IMC). This additional cavity selects the optical fundamental mode (the Gaussian TEM00 mode), suppressing the high-order modes. The IMC is also used as a reference to pre-stabilize the laser beam frequency. The IMC length is stabilized in the low frequency range (below a few tens of Hz, where seismic noise and other spurious mechanisms induce fluctuations of the cavity length) by using as a reference a rigid 30 cm-long reference cavity (RFC). After the IMC, the beam passes through the power recycling mirror (PR), is separated by the beam splitter (BS) and enters the two 3km long Fabry-Perot cavities. The power recycling mirror forms an additional Fabry-Perot cavity between the whole interferometer and itself. In this way the power impinging onto the BS is amplified by a factor of 50. The output interference signal is reconstructed by the photodiode B1, made by a set of high-quantum efficiency photodiodes. The output beam, before reaching B1, passes through a monolithic 2.5 cm-long cavity (output mode cleaner -OMC). The OMC is designed to filter high-order optical modes, originating from misalignments and optical defects. The other photodiodes (labeled by B in Fig. 2) are used as feedback error signals to fix the longitudinal lengths of the interferometer (cavity resonance condition and destructive interference on B1) with a very high level of accuracy. In order to optimize the contrast in the interference pattern, the interferometer mirrors must be aligned with each another and with respect to the beam with a nanoradian accuracy. This is done using a feedback based on the error signals coming from the quadrant photodiodes (labeled by Q in Fig. 2). All the six main Virgo mirrors: Power Recycling, Beam Splitter, North Input, North End, West Input, West End (see Fig. 2 with obvious notations) are suspended from a superattenuator (see Fig. 3). In order to reduce the variations of the refraction index due to the gas density fluctuations the entire interferometer must be kept in the vacuum. For this reason, each of the long Fabry-Perot cavities is contained in a 3 km-long vacuum pipe, with a diameter of 1.2 m. The seismic isolation is provided by passive five pendulum system called the superattenuator (see Fig. 3 the plot on the left) what allows a very large suppression of the thermal noise by more than 10 orders of magnitude starting from a few Hz (see Fig. 3 the plot on the right).

Virgo upgrades

The commissioning of the Virgo detector lasted from the year 2003 to 2007. In 2007 from 18th of May till 1st of October the first Virgo scientific run (VSR1) took place (136 days) (see [4,5]). At the end of VSR1, in October 2007, an intense program of upgrades and commissioning started to lead the detector towards the Virgo+ configuration. The main upgrades regarded the installation of a better and less noisy read-out and control electronics, the installation of a more powerful laser amplifier and some upgrades of the injection bench necessary to cope with the higher laser power and to provide a better seismic noise rejection. Moreover, a thermal compensation system (TCS) [START_REF] Accadia | A Thermal Compensation System for the gravitational wave detector Virgo[END_REF] has been installed to reduce thermal effects in the input mirrors. TCS uses a CO 2 beam that heats the peripheral of the input test masses in order to compensate for the deformation induced in the mirror central area by the heat deposited by the main mirror. The commissioning activity allowed to increase the input power from 8 W, used during VSR1, to 17 W. After these upgrades Virgo performed the second science run (VSR2) that lasted from 7th of June 2009 till 7th of January 2010 (183 days) (see [6]). In Figure 4 we compile sensitivities of the Virgo detector during various stages of commissioning and the science run. We note that the measured Virgo sensitivity towards the end of VSR2 was very close to the design curve. After the end of VSR2 run Virgo has started the installation of monolithic suspensions leading to Virgo+MS configuration (see [7,8]). This should allow a reduction of thermal noise level in the frequency region around 30-40 Hz. If combined with an increase of the cavity finesse and with the replacement of the test masses with new mirrors exhibiting a lower thermal noise level, it is possible to extend several times the horizon distance for the detection of compact coalescing binaries. In order to have a fully monolithic stage, fused silica wires have to be properly attached to the mirror. This is possible by means of suitable silica supports (called ears) bonded to the mirror sides through the silicate bonding technique [START_REF] Gwo | Ultra precision and reliable bonding method[END_REF][START_REF] Gretarsson | [END_REF]12]. Moreover, they have to be clamped in a proper way to the upper stage of suspension, minimizing the impact on the overall suspension design (see Figure 5). The installation of monolithic suspensions was successful but unfortunately it turned out that the radius of curvature (ROC) of the NE end mirror was shorter that that of the WE mirror by 110m. This led to more total light at the output port (greater contrast defect) and thus more scattered light in the detection bench. As a result the power of the light at the dark fringe was around 3 watts (ten times larger than in Virgo). The main contribution of the noise has come from the beam reflected by the output mode cleaner. Consequently this beam was dumped outside the vacuum. However the scattering noises still occurred originating probably at the output window and on the dumper itself. Despite these problems in order to take data in coincidence with the LIGO detectors Virgo has started the third science run (VSR3). After the closing of VSR3, the first action will be to dump under vacuum the beam most critical for the resulting scattered light. Then a first short campaign of measurements in the 150-300 Hz region will be done. After that it is expected to install the system for the radius of curvature compensation. It has been decided to increase the radius of curvature of the NE mirror to match that of WE mirror by frontal heating. These actions should result in an improved sensitivity and another data run -VSR4 is planned in the mid 2011, to be followed by the start of the Advanced Virgo installation. It is still not possible to predict what the sensitivity of the Virgo detector will be during the VSR4 data run.

Advanced Virgo

The Advanced Virgo funding has been approved by INFN and CNRS at the end of 2009. In order to increase the interferometer sensitivity at higher frequencies the laser input power will be around 200 W (with 125 W injected into the interferometer). The baseline design [START_REF]The Virgo Collaboration Advanced Virgo Baseline Design[END_REF] foresees the use of a solid state laser composed by a stabilized master laser followed by two stages of amplification. To cope with the larger radiation pressure effects due to the larger power injected the heavier test masses (42 kg) will be used, and as in the Virgo+MS, they will be suspended through the fused silica fibers. The installation of heavier monolithic suspension mirrors will further increase sensitivity below 50Hz with respect to the Virgo+MS configuration. To this extent, the experience done with the Virgo+MS payloads will be precious to understand all the features of this technology, improve it further and reduce the risk for the advanced detectors. The optical scheme is modified by the introduction of a signal recycling cavity. The use of signal recycling [START_REF] Meers | [END_REF] and of the resonant sideband extraction scheme allows widening the detector bandwidth thus extending the sensitivity into the kHz region. By changing the position of the signal recycling mirror one can optimize the sensitivity of the detector for various gravitational wave sources. Also the finesse of the 3 km Fabry-Perot cavities will be larger (around 900 in the baseline). A DC detection scheme will be adopted to reduce some technical noises instead of the RF scheme used in the initial Virgo. The vacuum system and the infrastructures will be also upgraded to improve the sensitivity in the low and mid frequency range. Large cryotraps will be installed at the extremes of the 3 km vacuum pipes to isolate them from the rest of the vacuum system. This, combined with the baking of the tubes, will allow reducing the residual gas pressure to the target of 10 -9 mbar. To reduce the risk of acoustic couplings, the air conditioning machines as well as several other sources of acoustic noise will be moved out of the central experimental hall. The reference sensitivity for Advanced Virgo in comparison with design Virgo+ and Virgo+MS sensitivities is shown in Figure 6. Around 100 Hz the main limitation to the sensitivity is due to the thermal noise in the mirror coatings. The sensitivity shown in the Figure 6 assumes current coating technology. Any further improvements from the ongoing R&D will have a direct positive impact on the detector sensitivity. The effect of coating thermal noise is minimized running the Fabry-Perot cavities near the co-focal configuration thus maximizing the beam size on the mirrors.

According to the present planning Virgo+ will be shut down in the second half of 2011 and the installation of Advanced Virgo will start. The commissioning of the interferometer should start in 2014 with the goal of having a first stable 1-hour lock in 2015.

Virgo performance

The most promising source of gravitational waves that can be detected with ground based laser interferometers is the coalescence of compact binaries consisting of neutron stars and/or black holes. Thanks to intensive research of relativists, astrophysicists and computer scientists we can predict the gravitational wave signal from a coalescing binary extremely well [15,16]. This signal sweeps through the detector frequency band and the range to which a signal could be detected provides a very good overall characteristic of the performance of the detector. The basic quantity is the horizon distance which is the distance to an optimally oriented binary source that can be detected with signal-to-noise ratio (SNR) equal to 8 (see [17] Sec. III). A commonly 1.2 × 10 -3 1.9 × 10 -3 used characteristic is the sensemon range defined as the radius of a sphere whose volume is equal to the volume in which an interferometer could detect a source at SNR = 8, taking all possible sky locations and orientations into account. The sensemon range is smaller than the horizon distance by factor of around 2.26. In Figure 7 we have shown evolution of the sensemon range during the Virgo data taking VSR1 and VSR2.

An uncertain factor about the detection of coalescing compact binaries is the rate of occurrence of these sources (see [17] for a comprehensive discussion of the current understanding of the population of these sources in our Universe). In Tables 1 and2 we have presented sensemon ranges H in Mpc and estimated detection rates R in number of sources per year during the three Virgo science runs and for three design sensitivities of Virgo detector. We have used so-called realistic rates of compact binary coalescences summarized in Table IV of [17]. We see that with VSR1 and VSR2 data detection of a coalescing binary gravitational wave signal is very unlikely however it should be very common with the Advanced Virgo detector. The Virgo data, together with the LIGO and GEO600 data, are searched for gravitational wave signals from all types of astrophysical sources: coalescing binaries, supernovae, rotating neutron stars, early Universe. So far there were no detections but a number of astrophysically significant limits is being imposed [18,19,20,21,22,23]. This is consistent with the present sensitivity of the Virgo detector and the current astrophysical understanding of the gravitational wave generation mechanisms. For example with a very good sensitivity of the Virgo detector at low frequencies the spin down limit for the Vela pulsar will certainly be beaten. Virgo together with LIGO detectors is also receiving and providing triggers from coincident searches with other astronomical projects: gamma ray burst detectors [19,21], wide-field optical telescopes and high energy neutrinos detectors. In particular Virgo detector is indispensable in obtaining position in the sky of the triggers because this requires data from at least three detectors.

Figure 1 .

 1 Figure 1. An aerial view of the Virgo gravitational wave detector. The detector Virgo is located in the countryside of Commune of Cascina, a few km south of the city of Pisa, Tuscany.

Figure 2 .

 2 Figure 2. The optical layout of the Virgo detector.

Figure 3 .

 3 Figure 3. The left panel is the image of the entire Virgo superattenuator. The right panel presents comparison of the spectral density of seismic noise at the ground and that at the mirror. The Virgo superattenuator provides suppression of the amplitude spectral density of noise by 15 orders of magnitude at 10 Hz frequency.

Figure 4 .

 4 Figure 4. Amplitude spectral density of noise of the Virgo detector during various stages of commissioning and during the science runs VSR1 and VSR2 in comparison to Virgo+ design sensitivity curve.

Figure 5 .

 5 Figure 5. Monolitic suspension. The images, looking from the left, are respectively: the mirror with two ears silicate bonded to its side, silica wire with the upper end welded to the silica cone and the lower ended welded to the silica anchor, mirror suspended by four wires using anchors, close up of the anchor attachment, close up of the cone suspension, and the suspended mirror in position at the Virgo site.

Figure 6 .

 6 Figure 6. Design sensitivities of the Virgo detector.

Figure 7 .

 7 Figure 7. Sensemon range during VSR1 (left panel) and VSR2 (right panel). On the left panel two independent estimations of the sensemon range are displayed.

Table 1 .

 1 Expected horizons and detection rates of coalescing binaries during the two Virgo science runs. Actual sensitivities reached will depend on the real performance of the detectors.

	Run	NS-NS	NS-BH	BH-BH
	VSR1
	H [Mpc]	4.0	7.9	18
	R [no./yr] 3.1 × 10 -4	7.1 × 10 -5	1.0 × 10 -4
	VSR2
	H [Mpc]	9.8	20	46
	R [no./yr] 4.5 × 10 -3

Table 2 .

 2 Expected detection rates of coalescing binaries for Virgo design sensitivities.

	Design	NS-NS	NS-BH	BH-BH
	Virgo+
	H [Mpc]	14	28	65
	R [no./yr]	1.3 × 10 -2	3.3 × 10 -3	5.2 × 10 -3
	Virgo+MS
	H [Mpc]	50	110	250
	R [no./yr]	6.1 × 10 -1	1.7 × 10 -1	3.2 × 10 -1
	AdVirgo
	H [Mpc]	150	320	730
	R [no./yr]	17	4.7	7.6

PACS numbers: 04.80.Nn, 95.55.Ym

Acknowledgments

The authors acknowledge the support of the Italian Istituto Nazionale di Fisica Nucleare and the French Centre National de la Recherche Scientifique for the construction and operation of the Virgo detector. The authors also gratefully acknowledge the support of the research by these agencies and by the Foundation for Fundamental Research on Matter supported by the Netherlands Organization for Scientific Research, the Polish Ministry of Science and Higher Education, the FOCUS Programme of Foundation for Polish Science.


Luca Castelli Aleardi

Olivier Devillers

Éric Fusy

Canonical ordering for triangulations on the cylinder, with applications to periodic straight-line drawings

Keywords: triangulations, graph drawing, flat torus triangulations, tracé de graphe, tore plat

We extend the notion of canonical orderings to cylindric triangulations. This allows us to extend the incremental straight-line drawing algorithm of de Fraysseix et al. to this setting. Our algorithm yields in linear time a crossing-free straight-line drawing of a cylindric triangulation T with n vertices on a regular grid Z/wZ × [0, h], with w ≤ 2n and h ≤ n(2d + 1), where d is the (graph-) distance between the two boundaries. As a by-product, we can also obtain in linear time a crossing-free straight-line drawing of a toroidal triangulation with n vertices on a periodic regular grid Z/wZ × Z/hZ, with w ≤ 2n and h ≤ 1 + n(2c + 1), where c is the length of a shortest non-contractible cycle. Since c ≤ √ 2n, the grid area is O(n 5/2 ).

Ordre canonique pour des triangulations du cylindre et applications au tracé linéaire de graphes périodiques

The problem of efficiently computing straight-line drawings of planar graphs has attracted a lot of attention over the last two decades. Two combinatorial concepts for planar triangulations turn out to be the basis of many classical straight-line drawing algorithms: the canonical ordering (a special ordering of the vertices obtained by a shelling procedure) and the closely related Schnyder wood (a partition of the inner edges of a triangulations into 3 spanning trees with specific incidence conditions). Algorithms based on canonical ordering [START_REF] De Fraysseix | How to draw a planar graph on a grid[END_REF][START_REF] Kant | Drawing planar graphs using the canonical ordering[END_REF] are typically incremental, adding vertices one by one while keeping the drawing planar. Algorithms based on Schnyder woods [START_REF] Schnyder | Embedding planar graphs on the grid[END_REF] are more global, the (barycentric) coordinates of each vertex have a clear combinatorial meaning (typically the number of faces in certain regions associated to the vertex). Algorithms of both types make it possible to draw in linear time a planar triangulation with n vertices on a grid of size O(n × n). They can also both be extended to obtain (weakly) convex drawings of 3-connected maps on a grid of size O(n × n). The problem of obtaining planar drawings of higher genus graphs has been addressed less frequently [START_REF] Kocay | Drawing graphs on the torus[END_REF][START_REF] Gortler | Thurston Discrete one-forms on meshes and applications to 3D mesh parameterization[END_REF][START_REF] Mohar | Straight-line representations of maps on the torus and other flat surfaces[END_REF][START_REF] Mohar | Tessellation and visibility representations of maps on the torus[END_REF][START_REF] Chambers | Drawing graphs in the plane with a prescribed outer face and polynomial area[END_REF][START_REF] Duncan | Planar drawings of higher-genus graphs[END_REF][START_REF] Zitnik | Drawing graphs on surfaces[END_REF], from both the theoretical and algorithmic point of view. Recently some methods for the straight-line planar drawing of genus g graphs with polynomial grid area have been described in [START_REF] Chambers | Drawing graphs in the plane with a prescribed outer face and polynomial area[END_REF][START_REF] Duncan | Planar drawings of higher-genus graphs[END_REF] (to apply these methods the graph needs to be unfolded planarly along a cut-graph). However it does not yield (at least easily) periodic representations: for example, in the case of a torus, the boundary vertices (on the boundary of the rectangular polygon) might not be aligned, so that the drawing does not give rise to a periodic tiling.

Our main contribution is to generalize the notion of canonical ordering and the incremental straight-line drawing algorithm of de Fraysseix et al [START_REF] De Fraysseix | How to draw a planar graph on a grid[END_REF] to triangulations on the cylinder. The obtained straight-line drawing of a cylindric triangulation T with n vertices is x-periodic, on a regular grid of the form Z/wZ × [0, h], with w ≤ 2n and h ≤ n(2d + 1), where d is the (graph-) distance between the two boundaries. By a reduction to the cylindric case (the reduction is done with the help of a so-called tambourine [START_REF] Bonichon | Edge partition of toroidal graphs into forests in linear time[END_REF]), we can also obtain a straight-line drawing of a toroidal triangulation T with n vertices on a grid Z/wZ×Z/hZ, with w ≤ 2n and h ≤ 1+n(2c-1), where c is the length of a shortest non-contractible cycle. Since c ≤ (2n) 1/2 as shown in [START_REF] Albertson | On the independence ratio of a graph[END_REF], we have h ≤ (2n) 3/2 , so that the grid area is O(n 5/2 ).

For the toroidal case we mention that a notion of canonical ordering has been introduced in [START_REF] Castelli-Aleardi | Schnyder woods for higher genus triangulated surfaces, with applications to encoding[END_REF] (this actually works in any genus and yields an efficient encoding procedure) but we do not use it here. We also mention that, independently, an elegant periodic straight-line drawing algorithm for toroidal triangulations has been very recently described in [START_REF] Gonçalves | Toroidal maps : Schnyder woods, orthogonal surfaces and straightline representation[END_REF], based on so-called toroidal Schnyder woods and face-counting operations; in their case the area of the periodic grid is O(n 4 ).

Preliminaries

Graphs embedded on surfaces. A map of genus g is a graph (cellularly) embedded on the closed surface of genus g. The map is called planar for g = 0 (embedding on the sphere) and toroidal for g = 1 (embedding on the torus). The dual of a map G is the map G * representing the adjacencies of the faces of G, i.e., there is a vertex v f of G * in each face f of G, and each edge e of G gives rise to an edge e * in G * : if f and f ′ are the faces on each side of e then e * connects v f to v f ′ . A cylindric map is a planar map with two marked faces B 1 and B 2 whose boundaries C(B 1 ) and C(B 2 ) are simple cycles (possibly C(B 1 ) and C(B 2 ) share vertices and edges). The faces B 1 and B 2 are called the boundary-faces. Boundary vertices and edges are those belonging to C(B 1 ) (black circles in Fig. 1) or C(B 2 ); (red circles in Fig. 1) the other ones are called inner vertices (white circles in Fig. 1) and edges. Periodic drawings Here we consider the problem of drawing a cylindric (resp. toroidal) triangulation on the flat cylinder (resp. flat torus). The flat cylinder is a rectangle with a pair of opposite sides identified; the flat torus is a rectangle with both pairs of opposite sides identified. We classically require coordinates to be integers. So for a cylindric triangulation we aim at a crossing-free straight-line drawing on a regular (x-periodic) grid of the form Z/wZ×[0, h], and for a toroidal triangulation we aim at a crossing-free straight-line drawing on a regular (x-periodic and y-periodic) grid of the form Z/wZ × Z/hZ.

Periodic drawings of cylindric triangulations

We introduce at first a notion of canonical ordering for cylindric triangulations:

C(B 1 ). A vertex v ∈ C k is free if v is incident to no chord of C k and if v / ∈ C(B 1 ) (see Fig. 2 top left).
The shelling procedure goes as follows (n is the number of vertices in G\C(B 1 )): for k from n to 1, choose a free vertex v on C k , assign v k ← v, and then delete v together with all its incident edges. The existence of a free vertex at each step follows from the same argument as in the planar case [START_REF] Brehm | 3-orientations and Schnyder 3-Tree decompositions[END_REF]. Indeed, if there is no chord incident to C k , then any vertex v ∈ C k is free, while if there is a chord e for C k , then the set of chords incident to C k forms a system of archs (relative to C k ). If we look at a chord e = {u, v} that is "innermost" (i.e., no other chord is nested inside e), then the path between u and v on C k contains at least one vertex, which has to be free (see Fig. 2 top right). Underlying forest and dual forest. Given a cylindric triangulation G (with boundary faces B 1 and B 2 ) endowed with a canonical ordering π, define the underlying forest F for π as the oriented subgraph of G where each vertex v ∈ C(B 2 ) has outdegree 0, and where each v / ∈ C(B 2 ) has exactly one outgoing edge, which is connected to the adjacent vertex of v of largest label in π. (The forest F can be computed on the fly during the shelling procedure: when treating a free vertex v with neighbours c p , . . . , c q from left to right, add the edges {c i , v} to F , these edges being oriented toward v.) Since the edges are oriented in increasing labels, F is an oriented forest; it spans all vertices of G\C(B 2 ) and has its sinks on C(B 2 ). The augmented map G is obtained from G by adding a vertex w 1 inside B 1 , a vertex w 2 inside B 2 , and connecting all vertices around B 1 to w 1 and all vertices around B 2 to w 2 (thus triangulating the interiors of B 1 and B 2 , see Fig. 2 bottom middle).Define F as F plus all edges incident to w 1 and all edges incident to w 2 . Define the dual forest F * for π as the graph formed by the vertices of G * (the dual of G) and by the edges of G * that are dual to edges not in F . Since F is a spanning

B 1 B 2 v C 6 C 7 v e v w 2 w 1 w 1 w 1 w 1 F F * edge of F
P ℓ P r c p c q
e r e ℓ Figure 3: One step of the incremental drawing algorithm. Two vertical strips of width 1 (each one along a path in the dual forest) are inserted in order to make the slopes of e ℓ and e r smaller than 1 in absolute value. Then the new vertex and its edges connected to the upper boundary can be drawn in a planar way. connected subgraph of G, F * is a spanning tree of G * . Precisely each of the trees (connected components) of F * is naturally rooted at a vertex "in front of" each edge of B 1 , and the edges of the tree can naturally be oriented toward this root-vertex (see Fig. 2

bottom right).

Drawing algorithm. Given a cylindric triangulation G with no chordal edge incident to B 1 , we first compute a canonical ordering of G, and then draw G in an incremental way. We start with a cylinder of width 2|C(B 1 )| and height 0 (i.e., a circle of length 2|C(B 1 )|) and draw the vertices of C(B 1 ) equally spaced on the circle (space 2 between two consecutive vertices). Then the strategy is -for each k ≥ 1-to compute the drawing of G k out of the drawing of G k-1 by first stretching the cylinder (increasing the width by 2) and then placing the vertex v k and its incident edges (in G k ) in a planar way. Define the x-span of an edge e in the cylindric drawing as the number of columns [i, i + 1] × [0, +∞] that meet the interior of e (we have no need for a more complicated definition since, in our drawings, a column will never meet an edge more than once).

Consider the dual forest F * for the canonical ordering restricted to G k-1 . Let c p , c p+1 , . . . , c q be the path of C k-1 such that C k-1 is on the left of the path taking from c p to c q . Let e ℓ be the edge {c p , c p+1 } and e r be the edge {c q-1 , c q } (note that e ℓ = e r if q -p = 1). Let P ℓ (resp. P r ) be the path in F * from e * ℓ (resp. e * r ) to the root in its connected component (which is a vertex "in front of" an edge of B 1 )). We stretch the cylinder by inserting a vertical strip of length 1 along P ℓ and another along P r (see Fig. 3). The effect is exactly to increase by 1 the x-span of each edge dual to an edge in P ℓ , and then to increase by 1 the x-span of each edge dual to an edge in P r (note that P ℓ and P r are not necessarily disjoint, in which case the x-span of an edge dual to an edge in P ℓ ∩ P r is increased by 2, see Fig. 7 second on line3).After these stretching operations, whose effect is to make the slopes of e ℓ and e r strictly smaller than 1 in absolute value, we insert (as in the planar case) the vertex v k at the intersection of the ray of slope 1 starting from c p and the ray of slope -1 starting from c q , and we connect v k to c p , . . . , c q by segments 1 . These two 1 In the de Fraysseix et al algorithm for planar triangulations, the step to make the (absolute value of) slopes of e ℓ and er smaller than 1 is formulated as a shift of certain subgraphs described in terms of the underlying forest F . The extension of this formulation to the cylinder would be quite cumbersome. We find the alternative formulation as strip insertions more convenient for the cylinder (it also gives rise to a very easy linear implementation). 2) to compute an x-periodic drawing of a cylindric triangulation (no chordal edges incident to C 0 ). The vertices are treated in increasing label (the canonical ordering is the one computed in Fig. 2).

rays actually intersects at a grid point since the Manhattan distance between any two vertices on C k-1 is even.Fig. 7 shows the execution of the algorithm on the example of Fig. 1.

Proposition 2. For each cylindric triangulation G with no chordal edges incident to C(B 1 ), one can compute in linear time a crossing-free straight-line drawing of G on an x-periodic regular grid Z/wZ × [0, h] where -with n the number of vertices of G and d the (graph-)distance between the two boundariesw = 2n and h ≤ n(2d + 1), such that: every v ∈ C(B 1 ) has y(v) = 0 (so every edge in C(B 1 ) has slope 0), and every edge belonging to C(B 2 )\C(B 1 ) has slope ±1.

Proof. The fact that the drawing remains crossing-free relies on the slope-property for the upper boundary and on the following inductive property that is easily shown to be maintained at each step k from 1 to n:

Pl: for each edge e on C k (the upper boundary of G k ), let P e be the path in F * from e * to the root, let E e be the set of edges dual to edges in P e , and let δ e be any positive integer. Then the drawing remains planar when successively increasing by δ e the x-span of all edges of E e , for all e ∈ C k \{a, b}.

We now prove the bounds on the grid-size. If |C(B 1 )| = t then the initial cylinder is 2t × 0; and at each vertex insertion, the grid-width grows by 2. Hence w = 2n. In addition, due to the slope conditions (slopes of boundary-edges are at most 1 in absolute value), the y-span (vertical span) of every edge e is not larger than the current width at the time when e is inserted in the drawing. Hence, if we denote by v the vertex of C(B 2 ) that is closest (at distance d) to C(B 1 ), then the ordinate of v is at most d • (2n). And due to the slope conditions, the vertical span of C(B 2 ) is at most w/2 ≤ n. Hence the grid-height is at most n(2d + 1). The linear-time complexity is shown next.

Linear-time implementation. An important remark is that, instead of computing the xcoordinates and y-coordinates of vertices in the drawing, one can compute the y-coordinates of vertices and the x-span of edges (as well as the knowledge of which extremity is the left-end vertex and which extremity is the right-end vertex). In a first pass (for k from 1 to n) one computes the y-coordinate of vertices and the x-span r e of each edge e ∈ G at the time t = k when it appears on G k (as well one gets to know which extremity of e is the left-end vertex). Afterward, and if e / ∈ F , the x-span of e might further increase due to insertion of new vertices. Precisely let v j be a vertex inserted afterwards (i.e., j > t), let c p , . . . , c q be its neighbours in G j-1 from left to right, let e ℓ = {c p , c p+1 }, e r = {c q-1 , c q }, and let e ′ ℓ = {v j , c p } and e ′ r = {v j , c q }. Note that e is stretched due to the insertion of the strip along P ℓ iff either e = e ℓ or e ℓ is in the subtree of F * formed by the edges descending from e * . This happens iff e ′ ℓ is in the subtree T e of F * formed by the edges descending from e * . Similarly e is stretched due to the insertion of the strip along P r iff e ′ r is in T e . To state it more clearly, each edge in T e is responsible for an increase (by 1) of the x-span of e. Hence the total x-span of each edge e ∈ G is given by r e + s e , where s e = 0 if e ∈ F , and, if e / ∈ F , s e is the number of edges in T e . Since all quantities s e can easily be computed in linear time, this gives a linear implementation.

Allowing for chordal edges at B 1 . We finally explain how to draw a cylindric triangulation when allowing for chordal edges incident to C 0 = C(B 1 ); it is good to view B 2 as the top boundary-face and B 1 as the bottom-boundary face (and imagine a standing cylinder). For each chordal edge e of C 0 , the component under e is the face-connected part of G that lies below e; such a component is a quasi-triangulation (polygonal outer face, triangular inner faces) rooted at the edge e. A chordal edge e of C 0 is maximal if the component Q e under e is not strictly included in the component under another chordal edge. The size of such an edge e is defined as

|e| = |V (Q e )| -2.
(the size |e| is actually the width of the drawing of Q e using the de Fraysseix et al algorithm [START_REF] De Fraysseix | How to draw a planar graph on a grid[END_REF]). If we delete the component under each maximal chordal edge (i.e., delete Inria everything from the component except for the chordal edge itself) we get a new bottom cycle C ′ 0 that is chordless, so we can draw the reduced cylindric triangulation G ′ using the algorithm of Proposition 2. As we have seen in Section 3 (linear implementation paragraph), for each edge e of C ′ 0 , the initial x-stretch is r e = 2 and then the further increase s e of the x-stretch equals the number of edges descending from e * in the dual forest F * . Note that we have actually some freedom to choose the initial x-stretch r e of each edge on e ∈ C ′ 0 (just it has to be a positive even number, since at each step of the incremental algorithm the vertices of the current upper boundary have to be at even Manhattan distance). If e ∈ C 0 (i.e., e was not chordal in G) we take r e = 2. If e / ∈ C 0 (i.e., e was a maximal chordal edge in G), we take for r e the minimal even positive number such that r e + s e ≥ |e|, i.e., r e = 2 • max(1, ⌈(|e| -s e )/2⌉). Hence, at the end of the execution of the drawing of G ′ , the length ℓ e = r e + s e of each maximal chord e satisfies ℓ e ≥ |e|. Then for each maximal chord e of C 0 , we draw the component Q e under e using the planar algorithm by de Fraysseix et al [START_REF] De Fraysseix | How to draw a planar graph on a grid[END_REF]. this drawing has width |e|, with e as horizontal bottom edge of length |e| and with the other outer edges of slopes ±1. We shift the left-extremity of e so that the drawing of Q e gets width ℓ(e), then we rotate the drawing of Q e by 180 degrees and plug it into the drawing of G ′ (see Fig. 5). The overall drawing of G thus obtained is clearly planar. We obtain: Theorem 3. For each cylindric triangulation G, one can compute in linear time a crossing-free straight-line drawing of G on an x-periodic regular grid Z/wZ×[0, h], where -with n the number of vertices and d the (graph-) distance between the two boundariesw ≤ 2n and h ≤ n(2d + 1). The drawing is vertically convex (the intersection with each vertical line is a segment) and the slopes of boundary-edges are at most 1 in absolute value.

Periodic drawings of toroidal triangulations

For a toroidal triangulation G, a tambourine is a pair of parallel (i.e., homotopically equivalent) non-contractible oriented cycles Γ 1 and Γ 2 such that the edges arriving to Γ 1 from the right depart at Γ 2 and the edges arriving to Γ 2 from the left depart at Γ 1 It can be shown (see [START_REF] Bonichon | Edge partition of toroidal graphs into forests in linear time[END_REF] and the next paragraph) that for each non-contractible cycle Γ of G, there exists a tambourine whose two cycles are parallel to Γ. Deleting the edges that are strictly inside the tambourine, one obtains a cylindric triangulation G ′ with Γ 1 and Γ 2 as the contours of the boundary-faces. Note also that the distance d between Γ 1 and Γ 2 is smaller than the length of a shortest noncontractible cycle not parallel to Γ. We now apply the algorithm of Theorem 3 to G ′ . If augment the height h of the drawing to h ′ = h+w +1, and then wrap the x-periodic grid Z/wZ×[0, h] into a periodic grid Z/wZ × Z/h ′ Z, and finally insert the edges inside the tambourine as segments2 , then the slope properties (edges on Γ 1 and Γ 2 have slope at most 1 in absolute value while edges inside the tambourine have slope greater than 1 in absolute value) ensure that the resulting drawing is crossing-free (see Fig. 6).

An important remark is that we can choose Γ so that the graph-distance between the two boundaries Γ 1 and Γ 2 (in G ′ ) is smaller that the length γ of a shortest non-contractible cycle in G; and this choice for Γ can be done without computing a shortest non-contractible cycle. Let {Γ a , Γ b } be a basis of non-contractible cycles (which can be found in linear time by computing for instance a cut-graph). Denoting by Γ min a shortest non-contractible cycle of G, for sure at least one of Γ a or Γ b is not parallel to Γ min . Hence, for Γ a or for Γ b , the distance between the boundary-cycles (after deleting edges of the parallel tambourine) is smaller than |Γ min |. In other words if we choose the one cycle (among {Γ a , Γ b }) that yields the smaller distance between the two boundaries of G ′ , then this distance will be smaller than γ. We obtain:

Theorem 4. For each toroidal triangulation G, one can compute in linear time a crossing-free straight-line drawing of G on a periodic regular grid Z/wZ × Z/hZ, where -with n the number of vertices and γ the length of a shortest non-contractible cyclew ≤ 2n and h ≤ 1 + n(2γ + 1). Since γ ≤ √ 2n (as shown in [START_REF] Albertson | On the independence ratio of a graph[END_REF]), the grid area is O(n 5/2 ).

Existence of a tambourine. For the sake of completeness we include a proof of existence of a tambourine, which slightly extends the proof given in the master's thesis of Arnaud Labourel. A toroidal map is called weakly 3-connected if its periodic representation in the plane is 3-connected.

Let G be such a map and let Γ be a non-contractible cycle of G. We are going to show that G has a tambourine parallel to Γ. Let G ′ be the cylindric map obtained after cutting G along Γ; we take the annular representation of G ′ , calling Γ 1 (resp. Γ 2 ) the copy of Γ that is the outer (resp. inner) boundary. Let Γ ′ be the smallest (in terms of the enclosed area) cycle that strictly encloses Γ 2 (i.e., encloses Γ 2 and is vertex-disjoint from Γ 2 ). Let Γ ′′ be the largest (in terms of the enclosed area) cycle that is strictly enclosed in Γ ′ (i.e., is enclosed by Γ ′ and is vertex-disjoint from Γ ′ ). Note that by minimality Γ ′ has no chord inside, and by maximality Γ ′′ has no chord outside. Hence if we can show that there is no vertex in the area A (strictly) between Γ ′ and Γ ′′ then we can conclude that, in G, Γ ′ and Γ ′′ form a tambourine parallel to Γ. Assume there is a vertex v in A. Call vertex of attachment for Γ ′ a vertex w such that there is a path from v to w visiting only vertices of A before reaching w. Again by minimality of Γ ′ it is easy to see that there is a unique vertex of attachment v ′ for Γ ′ . Similarly (by maximality of Γ ′′ ) there is a unique vertex of attachment v ′′ for Γ ′′ . Let Γ v be the connected component of G ′ \{v ′ , v ′′ } that contains v. Then (again by minimality of Γ ′ and maximality of Γ ′′ ), Γ v has no cycle enclosing Γ ′′ . Hence (in the annular representation of G ′ ), there is a closed curve γ that meets G ′ only at the vertices v ′ , v ′′ and whose interior is made of the edges of Γ v only (so γ does not enclose Γ ′′ ). Such a curve yields a 2-separator in the periodic representation of G, a contradiction.

Allowing for non-contractible 1-and 2-cycles

A cylindric map with non-boundary faces that are triangles is called a weakly simple cylindric triangulation if cycles of length 1 or 2 have to separate the two boundary-faces, and if each vertex is incident to at most one loop. A toroidal map with triangular faces is called a weakly simple toroidal triangulation if cycles of length 1 or 2 are non-contractible and if there are no parallel loops incident to the same vertex. These are the necessary and sufficient conditions for the map to have no loop nor multiple edges in the periodic representation (hence these are the conditions under which one can aim at a periodic crossing-free straight-line drawing). For weakly simple cylindric triangulations without loops (nor chords incident to B 1 ), exactly the same shelling procedure and iterative drawing algorithm can be taken as for simple cylindric triangulations.

In case there are loops we have to explain how to deal with them. For the shelling procedure, if the current upper boundary C k is a loop -call v the incident vertex-then one deletes the loop and immediately takes v as the next free vertex (the fact that v is free is due to the fact that there is no other loop at v). In the drawing procedure (how to insert v and its incident loop into the drawing), one first adds v without its loop (by a classical one-step iteration of the drawing algorithm, involving two strip insertions), and then one draws the loop at v as an horizontal segment spreading over the whole width of the current periodic drawing (no strip insertion is done to draw the loop). Finally one can deal with chords incident to B 1 in the same way as for simple cylindric triangulations. About weakly simple toroidal triangulated maps, the procedure is also the same as for simple toroidal triangulations, since the above proof of existence of a tambourine holds in that case. And the grid bounds (whether for the cylindre or for the torus) are the same as for simple triangulations.

Figure 1 :

 1 Figure 1: A cylindric triangulation. Left: annular representation. Right: x-periodic representation.

Inria

Figure 2 :

 2 Figure 2: Shelling procedure to compute a canonical ordering of a given cylindric triangulation. The underlying forest is computed on the fly; the last drawing shows the underlying forest superimposed with the dual forest. The graph is the one of Fig. 1.

Inria

Figure 4 :

 4 Figure 4: Algorithm (Prop.2) to compute an x-periodic drawing of a cylindric triangulation (no chordal edges incident to C 0 ). The vertices are treated in increasing label (the canonical ordering is the one computed in Fig.2).

e 2 e 1 Figure 5 :

 15 Figure 5: Drawing a cylindric triangulation with chords at B 1 . To make enough space to place the component under e 2 , one takes 8 (instead of 2) as the initial x-span of e 2 .

Figure 6 :

 6 Figure 6: The main steps for drawing of a toroidal triangulation : 1) remove the edges inside a tambourine, (2) draw the obtained cylindric triangulation, 3) insert the edges of the tambourine back into the drawing.

Inria

2 2 1 Figure 7 :

 17 Figure 7: Top line: canonical ordering of a cylindric triangulation with non-contractible 1-and 2-cycles. Middle line: taking the vertices in increasing label, one can draw incrementally the cylindric triangulation. Bottom line: dealing with chordal edges.

  ≥ 0 the map G k induced by C(B 1 ) and by the vertices {v 1 , . . . , v k } is a cylindric triangulation. The other boundary-face (the one different from B 1 ) of G k , whose contour is denoted C k , contains B 2 in its interior.• The vertex v k lies on C k , and all its neighbors in G k-1 appear consecutively on C k-1 .

	Definition 1. Let G be a cylindric triangulation with boundary-faces B 1 and B 2 , and such that
	the cycle C(B 1 ) has no chords (i.e., there is no edge that is not on C(B 1 ) and has both ends
	on C(B 1 )). An ordering π = {v 1 , v 2 , . . . , v n } of the vertices of G\C(B 1 ) is called a (cylindric) canonical ordering if it satisfies:
	• For each k Shelling procedure. We now describe a shelling procedure to compute a canonical ordering
	of a cylindric triangulation G with boundary-faces B 1 , B 2 . At each step the graph formed by
	the remaining vertices is a cylindric triangulation, one boundary face remains B 1 all the way,
	while the other boundary-face (initially B 2 ) has its contour, denoted by C k , getting closer to

RR n°7989

We insert the edges in the tambourine T in the unique way such that, looking from bottom to top, at least one edge in T goes strictly to the right, and all edges going strictly to the right have x-span at most w; in this way it is easy to check that the x-span of all edges in T is at most w.RR n°7989

route des Lucioles -BP 93 06902 Sophia Antipolis Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

Acknowledgments

The authors thank D. Gonçalves and B. Lévêque, and (independently) B. Mohar for interesting discussions about toroidal Schnyder woods, and N. Bonichon for explanations on the computation of a tambourine in a toroidal triangulation.

This work is partially supported by ERC under the agreement ERC StG 208471 -ExploreMap.