Jieru Qiu

Liang Chen

Mengsi Zhan

Régis Laurent

Jérôme Bignon

Serge Mignani
email: serge.mignani@parisdescartes.fr

Xiangyang Shi
email: xshi@dhu.edu.cn

Anne-Marie Caminade

Jean-Pierre Majoral
email: majoral@lcc-toulouse.fr

Facile Synthesis of Amphiphilic Fluorescent Phosphorus Dendron-Based Micelles as Antiproliferative Agents: First Investigations

We designed and synthetized several families of original amphiphilic fluorescent phosphorus dendron-based micelles showing relevant antiproliferative activities for use in the field of theranostic nanomedicine. Based on straightforward synthesis pathways, twelve amphiphilic phosphorus dendrons bearing 10 protonated cyclic amino groups (generation one), or 20 protonated amino groups (generation two), and one hydrophobic chain carrying one fluorophore moiety were created.. These original dendron-based micelles showed moderate to high antiproliferative activities against a panel of tumor cell lines. This paper presents for the first time the synthesis and our first investigations of original phosphorus dendron-based micelles for cancer therapy applications.

Introduction

In medicine, nanotechnologies have sparked rapidly growing interest as a result of their potential to revolutionize conventional therapeutic treatments. Over the past several decades, many engineered soft nanoparticles have been used, such as protein-drug conjugates, liposomes, polymer nanoparticles, polymer-lipid nanoparticles, hydrogel-nanoparticles composite system, dendrimers and dendrons. Further, inorganic nanoparticles have been developed for various uses, including to enhance the effectiveness of cancer treatments. [START_REF] Kim | Recent progress in development of siRNA delivery vehicles for cancer therapy[END_REF][START_REF] Tran | Cancer nanomedicine: A review of recent success in drug delivery[END_REF] Among the soft nanoparticles, dendrimers and dendrons, which are tree-like macromolecules that contain a central core, pertain to the "nano-world" by virtue of their size and degree of branching. Properties of dendrimers including nanometric size, multivalence, branch density, flexibility, and surface properties can be controlled, and provide versatility to the final functionalization and surface charge of the dendrimers, which is a feature that is distinct from uncontrollable polymer networks. Consequently, their remarkable properties enable them to play an increasingly important part in a diverse range of applications, including nanomedicine as components in drug-delivery applications that require host-guest interactions.

Soft nanoparticles facilitate drug-loading either via their interior or peripheral regions. [START_REF] Ulbrich | Targeted drug delivery with polymers and magnetic nanoparticles: Covalent and noncovalent approaches, release control, and clinical studies[END_REF] For instance, polymeric micelles as micellar drug carriers are showing a high potential as nanomedicines to control the distribution of loaded bioactive molecules in the body as well as the biological activity based on adequate pharmacokinetic (PK) / pharmacodynamics (PD) behaviors. [START_REF] Cabral | Block copolymer micelles in nanomedicine applications[END_REF] Several clinical applications of polymeric micelles for the treatment of cancer were described, [START_REF] Varela-Moreira | Clinical application of polymeric micelles for the treatment of cancer[END_REF] such as the Phase II clinical trial of paclitaxel-loaded polymeric micelles against advanced pancreatic cancer. [START_REF] Saif | Phase II clinical trial of paclitaxel loaded polymeric micelle in patients with advanced pancreatic cancer[END_REF] Nowadays, no polymeric micelle has been developed as drug active per se. An avenue recently explored in nanomedicine, involves the use of dendrimers and dendrons as active drugs. [START_REF] Kim | Recent progress in dendrimer-based nanomedicine development[END_REF] Numerous families of dendrimers exist as for example poly(amidoamine) (PAMAM) dendrimers, [START_REF] Esfand | Poly(amidoamine) (PAMAM) dendrimers: From biomimicry to drug delivery and biomedical applications[END_REF] poly(propyleneimine) (PPI) dendrimers, [START_REF] Brabander Van Den Berg | Poly(propylene imine) dendrimers: Large-scale synthesis by hetereogeneously catalyzed hydrogenations[END_REF] poly(L-lysine) (PLL) dendrimers, [START_REF] Picart | Buildup mechanism for poly(L-lysine)/hyaluronic acid films onto a solid surface[END_REF] poly(L-ornithine) (PLO) dendrimers, [START_REF] Darrabie | Characteristics of poly-L-ornithine-coated alginate microcapsules[END_REF] carbosilane dendrimers, [START_REF] Zhou | Synthesis of novel carbosilane dendritic macromolecules[END_REF] phosphorus dendrimers. [START_REF] Launay | A general synthetic strategy for neutral phosphoruscontaining dendrimers[END_REF] Of all types of dendrimers, [START_REF] Caminade | Dendrimers: Towards catalytic, material and biomedical uses[END_REF] phosphorus dendrimers and dendrons appear to be among one of the most useful dendritic systems as a result of the extraordinary reactivity and versatility of phosphorus chemistry. [START_REF] Caminade | Phosphorous dendrimers in biology and nanomedicine: Syntheses, characterization, and properties[END_REF] Through an assessment of properties of phosphorus dendrimers used in nanomedicine, we can highlight their key roles as drugs with activities against cancer, [START_REF] Mignani | Original multivalent gold(III) and dual gold(III)copper(II) conjugated phosphorus dendrimers as potent antitumoral and antimicrobial agents[END_REF] neurodegenerative diseases, [START_REF] Wasiak | Phosphorus dendrimers affect alzheimer's (Aβ1-28) peptide and MAP-tau protein aggregation[END_REF][START_REF] Solassol | Cationic phosphorus-containing dendrimers reduce prion replication both in cell culture and in mice infected with scrapie[END_REF][START_REF] Klajnert | Influence of phosphorus dendrimers on the aggregation of the prion peptide PrP 185-208[END_REF][START_REF] Ottaviani | Time evolution of the aggregation process ofpeptides involved in neurodegenerative diseases and preventing aggregationeffect of phosphorus dendrimers studied by EPR[END_REF][START_REF] Wasiak | Cationic phosphorus dendrimers and therapy for Alzheimer's disease[END_REF][START_REF] Milowska | Phosphorus-containing dendrimers against α-synuclein fibril formation[END_REF][START_REF] Lazniewska | Mechanism of cationic phosphorus dendrimer toxicity against murine neural cell lines[END_REF][START_REF] Klajnert | EPR study of the interaction between dendrimers and peptides involved in Alzheimer's and prion diseases[END_REF] and inflammation. 25,26,27,,28 Further, it may mention their effectiveness for tolerogenic dendritic cells-based immunotherapy, [START_REF] Wei | Anticancer drug nanomicelles formed by self-assembling amphiphilic dendrimer to combat cancer drug resistance[END_REF] and the possibility to use them as nanocarrier [START_REF] Chen | Revisiting cationic phosphorus dendrimers as a nonviral vector for optimized gene delivery toward cancer therapy applications[END_REF] . Diverse types of fluorophores have been used as markers of phosphorus dendrimers, which include pyrene, naphthol, anthracene, dansyl, diketone, phthalocyanine, maleimide, julolidine, rhodamine, fluorescein or fluorene derivatives. [START_REF] Qiu | Fluorescent phosphorus dendrimers: Towards material and biological applications[END_REF] Fluorescent groups can be introduced onto the surface of dendrimers, linked to the core of dendrimers or attached to branches of dendritic structures. [START_REF] Caminade | Multicharged and/or water-soluble fluorescent dendrimers: Properties and uses[END_REF] The first aim of this original study was to prepare original dendron-based micelles with three series of amphiphilic fluorescent cationic phosphorus dendrons (generations 1 and 2) as anticancer agents active per se, that contain two types of protonated cyclic amino groups on their surfaces, namely pyrrolidine and piperidine, a hydrophobic chain that supports a fluorophore moiety such as pyrene and maleimide, and a non-fluorescent azabisdimethyl phosphonate group. In total, twelve macromolecules were prepared and fully characterized (Figure 1). Then, the capacity of amphiphilic dendrons to aggregate in solution, which was mediated by hydrophilic / hydrophobic interactions, to form polymeric micelles was characterized.

Lastly, we evaluated the anti-proliferative activities of particles against a panel of tumor cell lines including lung carcinoma A549, breast carcinoma MCF7, breast carcinoma metastasis MDA-MB-231, prostate carcinoma PC3, brain glioblastoma U87-MG, acute promyelocytic leukemia HL60, chronic myelogenous leukemia K562, myelogenous leukemia K562R (imatinib resistant), and colorectal carcinoma HCT116. This research is within our global research goal to develop novel nanotechnology-derived materials for the delivery of drugs, genes, and imaging molecules in the oncology domain.

Results and Discussion

Synthesis of amphiphilic phosphorus dendrons

All the reactions were monitored via 31 P NMR, and compounds were characterized using 31 P-NMR, 1 H-NMR, [START_REF] Launay | A general synthetic strategy for neutral phosphoruscontaining dendrimers[END_REF] C-NMR, and elemental analysis. UV-vis spectroscopic analysis was used to assess fluorescent macromolecules. Purification of the reaction mixture was performed using silica column chromatography. Phosphorus dendrimers are frequently synthesized using a method based on a divergent strategy that consists of the iteration of two key steps using commercially available hexachlorocyclotriphosphazene (P3N3Cl6) (1) as a core. [START_REF] Lartigue | Large dipole moments of phosphorus-containing dendrimers[END_REF] Fluorescent amphiphilic phosphorus dendrons, were formed with an asymmetric structure containing one hydrophobic fluorophore directly grafted to this core on one side, and five other groups that facilitated the development of dendron structures of generations 1 and 2 on the other side. As shown in Scheme 1, the starting point for the synthesis of fluorescent phosphorus dendrons was the preparation of the building block (3) obtained from (1), which involved grafting of five 4-hydroxybenzaldehyde (2). Then, the remaining P-Cl bond was modified via a substitution reaction to incorporate a fluorescent group, either phenol 4a or 4b, or a non-fluorescent group, phenol 4c. For this purpose, two fluorescent groups including 4-(1-pyrenyl) butyric acid (P) and 2,3-diphenyl maleic anhydride (D) as well as non-fluorescent azabisdimethylphosphonate (T) were prepared and reacted with tyramine to produce a functionalized pyrene monomer (4a), a maleimide functionalized monomer (4b) and an azabisdimethylphosphonate monomer (4c). Then, substituted phenols 4a-c were grafted on the core via nucleophilic substitution of the chlorine atom within THF or acetone solvent in the presence of cesium carbonate to produce 5a-c (83-85% yield). The next step involved a condensation of monomethylhydrazinodichlorothiophosphate (6) to five aldehyde end groups (compounds 5a-c) in chloroform in the presence of sodium sulfate at 0°C, which produced dendrons 7a-c with yields of 90% (7a), 91% (7b) and 84% (7c), respectively. The formation of amphiphilic dendrons requires two additional steps. First, nucleophilic substitution of -P(S)Cl2 end groups of 7a-c with 2-(pyrrolidin-1-yl)ethan-1-amine (8a) or 2-(piperidin-1-yl)ethan-1-amine (8b) give rise to generation 1 phosphorus dendrons including P1G1, D1G1, T1G1, P2G1, D2G1, and T2G1 at yields of 80-90%. These reactions occurred using ten equivalents of 8a or 8b in THF at 0°C in the presence of sodium sulfate and DIPEA (N, N-diisopropylethylamine).

The final step of the reactions involved protonation of P1G1, D1G1, T1G1, P2G1, D2G1, and T2G1 through addition of ten equivalents of hydrogen chloride in THF at 0 °C to produce P1G1.HCl, D1G1.HCl, T1G1.HCl, P2G1.HCl, D2G1.HCl, and T2G1.HCl at yields > 80%. As depicted in the Scheme 1, a similar strategy was used to prepare phosphorus dendrons of generation 2. The phosphorus dendrons of generation 2 were prepared from dendrons 7a-c, which were reacted with 10 equivalents of 4-hydroxy-benzaldehyde (2) in THF in the presence of cesium carbonate. This produced dendrons 9a-c at yields of 86-92%. Subsequently, condensation of the aldehyde end groups of 9a-c with 6, and subsequent addition of nanoparticles 7a, 7b or 7c (20 eq.) in the presence of sodium sulfate and DIPEA produced dendrons P1G2, D1G2, T1G2, P2G2, D2G2, and T2G2. These compounds were protonated with hydrogen chloride in THF at 0 °C to afford P1G2.HCl, D1G2.HCl, T1G2.HCl, P2G2.HCl, D2G2.HCl, and T2G2.HCl at generally good yields (> 50% for all three steps of synthesis).

Physical properties of original amphiphilic phosphorus dendron-based micelles

Twelve different amphiphilic phosphorus dendrons were produced throughout generations 1 and 2, eight of which As shown in Figure 3, the fluorescence spectra of amphiphilic pyrene dendrons reveal excitation bands at 330 and 345 nm, which is consistent with characteristic luminescence peaks typically observed for pyrene monomers.

Fluorescence after excitation at 345 nm produced emission bands at 379, 399 and 420 nm. No emission band was observed between 450 and 600 nm, which corresponds to emission patterns of pyrene excimers. The above results indicate that the grafting of pyrene to phosphorus dendrons does not seem to alter the fluorescent properties of pyrene. Also, the formation of pyrene dimers in the excited state, should greatly modify fluorescent wavelength as previously observed, [START_REF] Brauge | Segmental mobility in phosphoruscontaining dendrimers. Studies by fluorescent spectroscopy[END_REF] but is not observed in Figure 3. Characterization of the amphiphilic azabisdimethylphosphonate dendron (macromolecule T1G1.HCl) that lacked a hydrophobic fluorescent group was also examined for comparison. The UV-vis absorption spectrum of the dendron displayed a broad band around 283 nm which corresponded to aromatic groups of phosphorus dendron (Figure S3, supplementary information).

Self-assembled micelles are created from amphiphilic compounds that spontaneously form nanosized aggregates after individual surfactants are directly dissolved in aqueous solution above a threshold concentration (critical micelle concentration or CMC). [START_REF] Chakraborty | The methods of determination of critical micellar concentrations of the amphiphilic systems in aqueous medium[END_REF] A similar phenomenon can be expected with amphiphilic dendrons (Figure 4). self-assembled, since decreased I373/I393 ratios were observed, and CMC values were determined to be 76.9, 73.3, 35.3 and 26.3 µM respectively (Table 1). Low CMC values, such as those observed here, indicate that amphiphilic dendron micelles remain self-assembled under highly diluted conditions. In addition, our results demonstrated that amphiphilic maleimide dendrons of generation 2 have lower CMC values than their counterparts from generation 1 (D1G1.HCl > D2G1.HCl > D1G2.HCl > D2G2.HCl). Within each generation, the size and the protonation of the cyclic amino ring on the surface also affected steric hindrance (pyrrolidine < piperidine ring). As depicted in Table 1, determined CMC values of azabisdimethylphosphonate dendron (T) micelles followed similar trends as were described for maleimide dendrons (D)

previously, in which increased generation number corresponded to decreased CMC value. The higher values of CMC observed with the T series might be explained by the possible protonation of the nitrogen of the azabisphosphonate units which decrease the hydrophobicity of the core, as a consequence formation of micelles is less favorable. Similar to amphiphilic dendrons D and T, amphiphilic pyrene dendrons of series (P) of generation 2 had lower CMC values than those of previous generations. Interestingly, the I373 / I393 ratios decreased within the same generation, for D and T series dendrons relative to P series dendrons (e.g. T1G1.HCl > D1G1.HCl >> P1G1.HCl, T2G2.HCl > D2G2.HCl >> P2G2.HCl), which indicates that quenching effects occur in pyrene series dendrons. Interestingly, as shown in Figure 5, negligible differences between each micelle formed at different concentrations greater than CMC for the pyrene series were observed. This indicated that unimolecular micelles were formed and remained unaltered regardless of dilution (above the CMC), which is an attribute that has the potential to be highly useful for in vivo applications. In nanomedicine, hydrodynamic size and zeta potential are important general features of nanoparticles, particularly of micelles. These factors affect micelle cytotoxicity, intracellular uptake profiles, their capacities to release drugs to specific tissues, and pharmacokinetic (PK) / pharmacodynamics (PD) profiles. [START_REF] He | Effects of particle size and surface charge on cellular uptake and biodistribution of polymeric nanoparticles[END_REF] Dynamic light scattering (DLS)

and zeta potential measurements were used to determine the hydrodynamic size of amphiphilic dendron micelles formed from series (P, D and T) dendrons. An outstanding examination by Haag et al. [START_REF] Khandare | Multifunctional dendritic polymers in nanomedicine: opportunities and challenges[END_REF] revealed the relationship between the area under the curve (AUC) pharmacokinetic parameter and hepatic and renal clearance. Further, the researchers assessed the physicochemical properties (size and charge) of dendrimers. Neutral, amphiphilic, weak anionic and weak hydrophobic dendrimers displayed high plasma residence times and long half-lives, which corresponded to low clearance levels. [START_REF] Qiao | Synthesis and characterization of multi-functional linear-dendritic block copolymer for intracellular delivery of antitumor drugs[END_REF] A recent review by Mignani, Rodrigues, Shi and Majoral et al. assessed the key in-vivo factors important for the development of dendrimers for nanomedical applications. [START_REF] Mignani | Exploration of biomedical dendrimer space based on in-vivo physicochemical parameters: Key factor analysis (Part 2)[END_REF] As shown in Figure 6 (1) and Figure S6, the sizes of amphiphilic dendron micelles ranged from 200 to 500 nm, and increased with generation number. Micelles formed from amphiphilic dendrons containing protonated pyrrolidinium end groups were a bit larger than those formed from amphiphilic dendrons with protonated piperidinium groups of the same generation (micelles of P1G1.HCl > P2G1.HCl, D1G1.HCl > D2G1.HCl, D1G2.HCl > D2G2.HCl, and T1G1.HCl > T2G1.HCl). This trend was not observed when the micelle size of T1G2.HCl was compared with that of T2G2.HCl.

Polydispersity index (PDI) values of the twelve amphiphilic dendron micelles were assessed to range from 0.3 to 0.5, indicating that the mean particle size and homogeneity evaluated were valid (Table S1, supplementary information). To explore the stability of the T2G2.HCl micelles in both PBS and cell culture medium, their hydrodynamic sizes in both PBS and cell culture medium at 37 °C were monitored by DLS at different time points. As shown in Figure S7, the hydrodynamic size of T2G2 micelles remains constant for different time periods in both media, indicating their good colloidal stability.

The slightly larger hydrodynamic size in cell culture medium than that in PBS could be due to the slight protein adsorption, resulting in the formation of protein corona on the surface of the micelles.

Furthermore, the positive surface potential of amphiphilic dendron micelles is an important parameter, which affects their intracellular uptake efficiency and toxicity. The Figure 6 (2) shows the zeta potentials of all the twelve amphiphilic dendron micelles prepared. Zeta potentials determined for amphiphilic pyrene, amphiphilic maleimide, and amphiphilic azabisdimethylphosphonate dendron micelles were determined to be approximately 20, 40, and 36 mV, respectively. The mean diameters determined using TEM (see supplementary information, Figure S8) were approximately 30-40 nm for all micelles measured, and all were of uniform size distribution. TEM analysis revealed that the mean size of P1G1.HCl, P2G1.HCl, P2G2.HCl and D2G1.HCl micelles was 40, 28, 30 and 31 nm, respectively. Size determined via TEM was smaller than that determined via DLS (vide supra). Such a discrepancy can be reasonably expected as a result of differences between the hydrodynamic diameters of micelles in solution versus the sizes of dry/dehydrated micelles. 3 and Figure S11). Furthermore, the safety indexes of T2G2.HCl and DOX are shown in Table 4.

Antiproliferative activities of amphiphilic phosphorus dendron-based micelles

Obviously, T2G2.HCl micelles are much safer than free DOX when they treat A549, PC3, HCT116 and MDA-MB-231 tumor cell lines. To sum up, the T2G2.HCl micelles has a great potential to be used as a drug-free nanoplatform to cure these tumor cells with a high safety and antiproliferative activity.

Conclusion and perspectives

In medicine, nanotechnology has sparked rapidly growing interest as a result of its potential to solve important issues related to nanomedicine. Nanoformulations have already been used to improve cancer treatments, and several nanoformulated drugs have been FDA approved. Dendrimers represent a new generation of nanoparticle-based therapy.

In this article, we describe the straightforward synthesis, full characterization, and antiproliferative activities of novel amphiphilic fluorescent phosphorus dendron-based micelles active per se (generations one and two). These original macromolecules possess both protonated cyclic amino groups and a hydrophobic (fluorescent) moiety, and have the capacity to aggregate in solution via hydrophilic and hydrophobic interactions, which facilitate the formation of polymeric micelles.

This first exploration fully encourages us to design and develop this type of new micelles with the aim to fully control their dimensions, shape and morphology to get nanodevices for in vitro and in vivo biological applications.

Interestingly, several compounds displayed significative antiproliferative activities against acute promyelocytic leukemia HL60, colorectal carcinoma HCT116, breast carcinoma metastasis MDA-MB-231, lung carcinoma A549 and brain glioblastoma U87-MG. The further studies will be to design phosphorus dendron-based micelles with better safety ratio by increasing the length and the nature (e.g. introduction of double bounds) of the chain between the fluorophore and the scaffold as well the nature of the amino groups on the surface. Numerous studies have been carried out to evaluate the in vitro and in vivo cytotoxicity of dendrimers using different cell lines, concentrations, incubation times, and assay methods. The cytotoxicity is strongly influenced by the nature of the functional groups on the dendrimer surface. In the cationic series, like our series presented in this paper, nitrogen functions with decreased basicity display lower cytotoxicity, because of their decreased interactions with cell membranes. , [START_REF] Mignani | Exploration of biomedical dendrimer space based on in-vivo physicochemical parameters: Key factor analysis (Part 2)[END_REF][START_REF] Mignani | Exploration of biomedical dendrimer space based on in-vitro physicochemical parameters: key factor analysis (Part 1)[END_REF] Another point, will be to evaluate the mechanism of action. Another point will be to evaluate the mechanism of action of these compounds and to determine in more details if they could induced apoptosis and or necrosis cell death. The presented original strategy regarding the development of amphiphilic fluorescent phosphorus dendron-based micelles constitutes a potentially new approach for treating different types of cancer.

The authors declare no competing financial interest.

Figure 1 .

 1 Figure 1. Chemical structure of prepared G1-2 amphiphilic phosphorus dendrons, P1G1.HCl, D1G1.HCl, T1G1.HCl, P2G1.HCl, D2G1.HCl, T2G1.HCl, P1G2.HCl, D1G2.HCl, T1G2.HCl, P2G2.HCl, D2G2.HCl, and T2G2.HCl.

Scheme 1 .

 1 Scheme 1. Synthetic pathways of P1G1.HCl, D1G1.HCl, T1G1.HCl, P2G1.HCl, D2G1.HCl, T2G1.HCl, P1G2.HCl, D1G2.HCl, T1G2.HCl, P2G2.HCl, D2G2.HCl, and T2G2.HCl.

Figure 2 .

 2 Figure 2. UV-vis absorption spectra of amphiphilic pyrene dendrons dissolved in water.

Figure 3 .

 3 Figure 3. Excitation and emission spectra of amphiphilic pyrene dendrons dissolved in water

Figure 4 .

 4 Figure 4. Self-assembly of amphiphilic dendrons to form nanostructured aggregates (micelles).

(

  P1G1.HCl, P2G1.HCl, P1G2.HCl, and P2G2.HCl), amphiphilic maleimide dendron D series (D1G1.HCl, D2G1.HCl, D1G2.HCl and D2G2.HCl) and azabisdimethylphosphonate dendron T series (T1G1.HCl, T2G1.HCl, T1G2.HCl, and T2G2.HCl) to self-assemble. Values were determined using pyrene as a fluorescent probe for D and T series. Amphiphilic pyrene dendron series (P) CMCs were determined via an assessment of their auto-fluorescence spectra. 37 CMC was determined by evaluating the ratio of fluorescence intensities measured at emission wavelengths of 373 nm (I373) and 393 nm (I393) for pyrene fluorescence bands at room temperature against the dendron concentration. I373 / I393 ratio decreases when hydrophobic domains are present in solution since amphiphilic phosphorus dendrons self-assemble into micelles. All tested amphiphilic maleimide phosphorus dendrons (compounds D1G1.HCl, D2G1.HCl, D1G2.HCl, and D2G2.HCl)

Figure 5

 5 Figure 5 CMC evaluation in the pyrene dendron series. Intensity ratios (I373/I393) as function of logarithm of amphiphilic pyrene dendron concentrations.

Figure 6 .

 6 Figure 6. Mean particle size (left) and the zeta potential (right) of the amphiphilic dendron micelles (mean ± SD, n = 3).

Figure 7 .

 7 Figure 7. TEM morphology of the amphiphilic fluorescent phosphorus dendron-based micelles.

Finally, the cytotoxicity

  of P1G1.HCl, D1G1.HCl, T1G1.HCl, P2G1.HCl, D2G1.HCl, T2G1.HCl, P1G2.HCl, D1G2.HCl, T1G2.HCl, P2G2.HCl, D2G2.HCl, and T2G2.HCl was assessed using a (3-(4,5-dimethylthiazol-2-yl)-5-(3carboxymethoxyphenyl)-2-(4-sulfophenyl)-2H-tetrazolium) cell viability assay that measured their effects on a panel of tumor cell lines including lung carcinoma A549, breast carcinoma MCF7, breast carcinoma metastasis MDA-MB-231, prostate carcinoma PC3, brain glioblastoma U87-MG, acute promyelocytic leukemia HL60, chronic myelogenous leukemia K562, myelogenous leukemia K562R (doxorubicin resistant due to high P-glycoprotein (PGP) expression), and colorectal carcinoma HCT116. The diploid human fibroblast cell culture line, MRC5, was used to perform safety profiles of compounds. IC50s values ranged between ~0.2 and 50 μM, and displayed great heterogeneity between the antiproliferative activities of compounds (see supplementary information). Taken together, antiproliferative activities of compounds against the HCT 116 cell line shown in the Table 2 reveal that dendrons (series P, D and T) containing piperidinium terminal groups (compounds P2G1.HCl, P2G2.HCl, D2G1.HCl, D2G2.HCl and T2G2.HCl) displayed higher cytotoxicity (IC50s ~ 0.2-1.3 µM) than corresponding dendrons containing pyrrolidinium terminal groups (compounds P1G1.HCl, P1G2.HCl, D1G1.HCl, D1G2.HCl, T1G1.HCl and T1G2.HCl, IC50s ~0.6-6 µM, IC50 of T1G1.HCl ~52 µM) created within the same generation.Cytotoxicity increased as generation increased. Compounds of generation 2 were more cytotoxic than those of generation 1, and compounds containing terminal piperidinium groups were particularly effective. This trend was not generally applicable for all cell lines. For instance, against the K562 cell line, the most cytotoxic compounds were those of generation 1. As such, the most potently cytotoxic dendrons were P2G1.HCl and D2G1.HCl (IC50s ~ 0.4-1 µM) of series P and D, but not series T. Concerning HL60 cell lines, no clear structure activity relationships were observed, and the most potent antiproliferative compound assessed was P2G1.HCl. Unlike doxorubicin (DOX), amphiphilic phosphorus dendrons displayed cell selectivity.

Table 1 .

 1 Critical micelle concentrations (CMC) of amphiphilic phosphorus dendrons in water.

				Azabisdimethyl
	CMC (μM)	Pyrene series (P)	Maleimide series (D)
				phosphonate series (T)
	Generation 1 with pyrrolidinium
		3.56 (P1G1.HCl)	76.9 (D1G1.HCl)	153.7 (T1G1.HCl)
	end groups

Table 1 ,

 1 CMC values in water[START_REF] Kalyanasundaram | Environmental effects on vibronic band intensities in pyrene monomer fluorescence and their application in studies of micellar systems[END_REF] were based on the capacities of amphiphilic pyrene dendron P series

Table 2 .

 2 Antiproliferative

			activities of phosphorus dendron micelles and DOX against HCT116, K562 and
	HCT116 tumor cell lines (IC50, µM).
			Antiproliferative activities IC50 (µM)
	Series	Compounds	HL60	K562	HCT116
		P1G1.HCl	1.17±0.13	4.62±0.16	1.54±0.12
	P	P2G1.HCl	0.28±0.06	0.36±0.02	1.07±0.05

Table 3 .

 3 Antiproliferative activities of T2G2.HCl and DOX against normal L929 cells, A549, MCF7, PC3, U87-T2G2.HCl showed broad antiproliferative activity against a panel of tumor cell lines as shown in

	MG, HL60, HCT116, K562, K562R and MDA-MB6231 tumor cell lines (IC50 µM).
		T2G2.HCl	DOX		T2G2.HCl	DOX
	L929	8.75±0.06	0.51±0.007 HL60	4.1±0.15	0.01±0.001
	A549	0.36±0.02	0.06±0.001	HCT116	0.86±0.02	0.09±0.003
	MCF7	2.89±0.17	0.12±0.009 K562	1.1±0.06	0.005±0.003
	PC3	0.56±0.03	0.10±0.003 K562R	2.47±0.07	>50
	U87-	0.27±0.03	0.01±0.002 MDA-MB-	0.31±0.01	0.03±0.002
	MG			231
	HL60	4.1±0.15	0.01±0.001
	Table 4 Safety indexes of T2G2.HCl and DOX against A549, MCF7, PC3, U87-MG, HL60, HCT116, K562,
	K562R and MDA-MB6231 tumor cell lines.
		T2G2.HCl	DOX			T2G2.HCl	DOX
	A549	24.31±1.18	8.5±0.03	HCT116	10.17±0.17	5.67±0.11
	MCF7	3.03±0.16	4.25±0.26	K562	7.95±0.38	102±9.34
	PC3	15.63±0.73	5.1±1.60	K562R	3.54±0.07	>0.010
	U87-MG	32.41±3.42	51±9.89	MDA-MB-231	28.22±0.71	17±0.90
	HL60	2.02±0.06	51±4.44

Table 3 .

 3 Indeed, strong antiproliferative activities were observed for T2G2.HCl against aggressive A549 (lung carcinoma), PC3 (prostate carcinoma), U87-MG (acute promyelocytic leukemia) and MDA-MB-231 (breast carcinoma metastasis) cells in which IC50 values produced were less than 0.4 µM. Importantly, T2G2.HCl effectively inhibited proliferation of MDA-MB-231(IC50 = 0.31 µM), which is a highly aggressive, invasive and poorly differentiated triple-negative breast cancer (TNBC) cell line. In TNBC, estrogen and progesterone receptors are negative, and treatment options for TNBC are limited. Surgery and chemotherapy, either individually applied, or used in combination, appear to be the only available means to treat the disease, and prognosis remains poor. 42 T2G2.HCl produced no adequate safety ratio versus the MRC5 cell line, which was derived from normal lung tissue. Very interestingly, T2G2.HCl displayed antiproliferative activity against K562R cell line which is resistant to DOX due to its strong PGP expression (IC50 > 50 µM). Meanwhile, T2G2.HCl micelles and free DOX showed IC50s of 8.75±0.06 and 0.51±0.007 µM against L929 cells, respectively (Table

Acknowledgements

This research has been financially supported by the NSFC-CNRS 2019 collaboration project (21911530230 for X.S. and 199675 for R.L., S.M., A.M.C. and J.P.M.), the PRC program NSCF-CNRS 2019 (A.M.C., J.P.M., S.M. and X.S.), the National Key R&D Program (2017YFE0196200 for X.S.), and the Sino-French Cai Yuanpei Programme. S.M. and X.S. acknowledge the support of FCT-Fundação para a Ciência e a Tecnologia (Base Fund UIDB/00674/2020 and Programmatic Fund UIDP/00674/2020, Portuguese Government Funds) and ARDITI-Agência Regional para o Desenvolvimento da Investigação Tecnologia e Inovação through the project M1420-01-0145-FEDER-000005-CQM+ (Madeira 14-20 Program). S.M. and J.P.M. acknowledge transnational EuroNanoMed III funded projects including a proper acknowledgement of ERANET EuroNanoMed III and the respective funding partner organizations. J.P.M., A.M.C. and R.L. thanks CNRS (France) for financial support.

Supplementary data:

The Supporting Information is available free of charge at https://pubs.acs.org/doi/10.1021/acs.bioconjchem.0c00716. 1. Synthesis and characterization; 2. UV-visible and fluorescence properties;3. Critical micelle concentration determination,4. Hydrodynamic size and zeta potential measurements;5. Transmission electron microscope, 6. Biological properties of original amphiphilic fluorescent phosphorus dendrons,7. References,,8. 31 P, 1 H, and 13 C NMR spectra, 7. Biological tests

AUTHOR INFORMATION

Corresponding Authors Serge Mignani


Luca Castelli

Olivier Devillers
email: olivier.devillers@sophia.inria.fr

Gilles Schaeffer
email: schaeffe@lix.polytechnique.fr

Succinct Representations of Planar Maps *

Keywords: Succinct data structures, graph encoding, data compression, planar maps, geometric data structures, triangulations

This paper addresses the problem of representing the connectivity information of geometric objects using as little memory as possible. As opposed to raw compression issues, the focus is here on designing data structures that preserve the possibility of answering incidence queries in constant time. We propose in particular the first optimal representations for 3-connected planar graphs and triangulations, which are the most standard classes of graphs underlying meshes with spherical topology. Optimal means that these representations asymptotically match the respective entropy of the two classes, namely 2 bits per edge for 3-connected planar graphs, and 1.62 bits per triangle or equivalently 3.24 bits per vertex for triangulations. These representations support adjacency queries between vertices and faces in constant time.

Introduction 1.Connectivity vs geometry

A geometric object is often represented by a polygonal mesh which contains two kinds of information: the geometry and the connectivity. The connectivity is a graph which describes how vertices are linked by edges and faces, while the geometry consists in the vertices coordinates. In usual representations such as VRML format or pointers representations in main memory [START_REF] Boissonnat | Triangulations in CGAL[END_REF], the connectivity is the most expensive part: it costs hundreds of bits per vertex while the geometry costs only tens of bits per vertex. As a matter of fact, in such formats where the connectivity is represented by numbering the vertices and giving indexes, the cost of connectivity has order Θ(n lg n). As done in previous existing works on compact representations [START_REF] -N Chuang | Compact encodings of planar graphs via canonical orderings and multiple parentheses[END_REF][START_REF] Munro | Succint representation of balanced parantheses and static trees[END_REF][START_REF] Blanford | Compact representations of separable graphs[END_REF], we shall concentrate in this paper on reducing the connectivity cost, and leave the problem of reducing the geometry cost aside. We observe however that our structure is compatible with several of the standard approaches to geometry compression (point coordinates can be given in a local framework).

Compression vs succinct structures

A geometric object can be represented either in a linear format for disk storage or network transmission, or stored in main memory for the exploration of the object. In the first case, reducing the size is called compression, and compressing the connectivity of various kind of meshes has been successfully attacked in recent years [START_REF] Poulalhon | Optimal coding and sampling of triangulations[END_REF][START_REF] Rossignac | Edgebreaker: Connectivity compression for triangle meshes[END_REF][START_REF] Keeler | Short encodings of planar graphs and maps[END_REF][START_REF] Turan | Succinct representations of graphs[END_REF][START_REF] Touma | Triangle mesh compression[END_REF][START_REF] Fusy | Dissections and trees, with applications to optimal mesh encoding and to random sampling[END_REF][START_REF] Khodakovsky | Near-Optimal Connectivity Encoding of 2-Manifold Polygon Meshes[END_REF] (for a survey of the most recent advances in this field we refer to [START_REF] Alliez | Recent advances in compression of 3d meshes[END_REF]). In this paper we deal with the second case of main memory representation, and our aim is to design a data structure having a small size and allowing to answer queries in constant time. Usual queries consist in going from a face to its neighbor or asking if two vertices are adjacent in the mesh. Such a structure is called succinct if the cost asymptotically matches the entropy of the class and compact if it matches it up to a constant factor. More precisely, given a class of objects with a size parameter n (e.g. the number of elements of some kind), we consider the number of objects of size n in the class. If this number has an exponential growth of order 2 αn when n goes to infinity, the entropy1 of the class is defined to be αn. A representation is then compact if it uses O(n) bits and succinct if it uses αn + o(n) bits. Observe that a correct representation cannot use less than αn bits for it must be possible to distinguish all objects.

General framework

The general framework we use for designing a compact or succinct data structure for a given class of objects of size n is sketched here:

• First the object is split into tiny pieces of size O(lg n), tiny meaning small enough so that a catalog of all possible pieces can be constructed in o(n) time and space. Then a tiny piece is represented by its index in the catalog, and the sum of the sizes of all indexes is expected to match the entropy of the class.

• The incidence relations describing how the splitting into tiny pieces has been done is encoded in a graph G of tiny pieces. Since there are O( n lg n ) tiny pieces with a linear number of incidences between them, a classical representation of this graph using pointers of logarithmic size costs O(n) and this approach already yields a compact data structure.

• Small pieces of O(lg 2 n) size are constructed by joining lg n tiny pieces, this allows to use pointers of size O(lg n) only between small pieces while adjacencies between tiny pieces are described with local pointers of size O(lg lg n). Since the number of small and tiny pieces are respectively O( n lg 2 n ) and O( n lg n ), this multi-level approach yields sublinear costs of O( n lg n lg 2 n ) and O( n lg lg n lg n ) for G, making the structure succinct.

Related results

We briefly review in this section a few results about representations of graph connectivity for 3-connected planar graphs and triangulations. These results can be given in terms of n the number of vertices, m the number of faces or e the number of edges. In the special case of triangulations of a topological sphere, 6n ≃ 2e = 3m and the entropy is 1.62m = 3.24n bits [START_REF] Tutte | A census of planar triangulations[END_REF]. For planar triangulations with a boundary, the entropy is 2.175m bits. For general 3connected planar graphs the entropy is 2e bits [START_REF] Tutte | A census of planar maps[END_REF].

On the practical side, classical main memory representations use pointers: n + 6m pointers are needed for triangulations and n + 6e for 3-connected graphs [START_REF] Boissonnat | Triangulations in CGAL[END_REF], where a pointer means 32 bits with real pointers and lg n bits using indexes. A cheaper solution with 2e pointers [START_REF] Kallmann | Star-vertices: a compact representation for planar meshes with adjacency information[END_REF] has been proposed with the price of a higher access cost to neighbors. None of these O(n lg n) structures are compact.

The above framework has been introduced for balanced parenthesis words (Dyck words) by Jacobson [START_REF] Jacobson | Space efficients static trees and graphs[END_REF] for the compact representation, and by Munro and Raman [START_REF] Munro | Succint representation of balanced parantheses and static trees[END_REF] for the succinct representation.

The size parameter of a parenthesis word is its number of characters and optimality means 1 bit per character. In this context the natural query is to ask for the matching parenthesis of the parenthesis at a given position. These results on parenthesis words allow for succinct representations of plane (aka ordered) trees using 2n bits. Then a planar map can be decomposed into several trees which can be succinctly represented.

However, this transformation from graphs to trees being non bijective, it yields representations for planar graphs that are not succinct but only compact. Along these lines, a representation of planar graphs using 2e + 8n bits was given [START_REF] Munro | Succint representation of balanced parantheses and static trees[END_REF] and then improved to 2e + 2n bits [START_REF] -N Chuang | Compact encodings of planar graphs via canonical orderings and multiple parentheses[END_REF][START_REF] Chiang | Orderly spanning trees with applications to graph encoding and graph drawing[END_REF].

In our previous work [START_REF] Castelli Aleardi | Succinct representation of triangulations with a boundary[END_REF], we have shown how to extend the framework so that it can be applied directly to triangulations with a boundary and provided a succinct representation for this (larger) class of triangulations. This approach was also successful in dealing with local dynamic updates of triangulations of higher genus surfaces [START_REF] Castelli Aleardi | Dynamic update of succinct triangulations[END_REF] (a comparison with previous works is shown in Table 1).

With a slightly different strategy, Blandford et al. [START_REF] Blanford | Compact representations of separable graphs[END_REF] showed how to design a compact data structure supporting adjacency and degrees queries on vertices for special classes of graphs having small separators. However this approach needs efficient algorithms for finding separators and the exact cost of the representation is difficult to characterize. As in previous works, our model of computation is a RAM machine, with O(1) time access on words of size Θ(lg n).

Contribution

The contribution of this paper is twofold. As far as results are concerned, we propose the first succinct data structures for representing planar triangulations without boundary (triangulations of a topological sphere) and 3-connected planar maps, as stated in Theorem 1 below.

Theorem 1. There exist succinct representations

• of planar triangulations (without boundaries) requiring asymptotically 1.62 bits per triangle,

• of 3-connected planar graphs requiring asymptotically 2 bits per edge.

Both representations support local standard navigation in O(1) time, using an extra storage of size O( n lg lg n lg n ). From the methodological point of view, we formalize the catalog-tiny-small framework. With respect to the seminal data structures proposed for words and trees [START_REF] Jacobson | Space efficients static trees and graphs[END_REF][START_REF] Munro | Succint representation of balanced parantheses and static trees[END_REF], and for triangulations in our paper [START_REF] Castelli Aleardi | Succinct representation of triangulations with a boundary[END_REF], the present framework makes explicit the local planarity properties on which the approach is based.

Furthermore it relaxes the property, central in those previous works, that tiny pieces should be taken in a class with the same entropy as the main class of objects represented. Finally, in order to develop our two new applications (triangulations and 3-connected planar maps), we design new splitting schemes.

Next section will formalize the catalog-tiny-small framework, while Section 3 describes its use for planar maps and Section 4 for triangulations.

The catalog-tiny-small framework

In this section we make gradually more precise the general framework sketched in Section 1. At a first level of details, the framework applies to any data structure which has linear entropy and can be decomposed into regions connected by a globally sparse graph: this includes parenthesis words, trees, and graphs on surfaces. The framework is then specialized to connectivity structures of meshes.

Additivity of the entropy and the catalog

In order to apply our framework to a class of combinatorial objects, we first need that the entropy be linear. More precisely consider a class C = (C n ) of objects where n is intended as a size parameter (the number of some elementary cells) and assume that the set C n of objects of size n has a finite cardinality In other terms, the cardinality of the class C n grows roughly like a simple exponential 2 αn , and αn bits are needed to index an arbitrary element. The constant α is sometimes called the entropy per size unit: α = 2 bits per node for binary trees, and, as indicated above, α = 1.62 bit per triangles for triangulations, and α = 2 bits per edge for 3-connected planar graphs. Observe however that some classes, like the classes of permutations of {1, . . . , n} or of general n-vertex graphs have non linear entropies: of order Θ(n lg n) and Θ(n 2 ) respectively.

We intend to decompose each object of C into pieces taken from a catalog of smaller objects: as opposed to previous works, we do not require that this catalog contains elements of C, but rather that it contains elements of a class D = (D m,k ), such that there exists a constant β and a positive function

g(m) = O(lg m) such that ||D m,k || ≤ αm + β k lg m + g(m) (1)
and

|D m,k | = 0 if k ≥ Km (for some constant K).
The objects of D m,k are intended to be used to describe tiny pieces of elements of C, with m the number of elementary cells, and k a parameter, called the number of sides, describing the complexity of the boundary of the piece. In the above bound the constant α is expected to be the same as for C n , and αm is the additive part of the entropy, while βk lg m is the extra amount of entropy due to the splitting into tiny pieces. By definition of the entropy, ||D m,k || bits are sufficient to index an element of D m,k in a table representing all those elements.

We assume more precisely that each element M of C n can be decomposed into • a collection (M 1 , . . . , M p ) of elements of D, with M j ∈ D nj ,kj for some n j , k j .

• and an oriented graph G with vertex set {N 1 , . . . , N p }, describing how the tiny pieces {M 1 , . . . , M p } are glued together to form M , in terms of adjacencies between sides of the M j .

More precisely, a vertex N j of G contains the following information:

-n j , k j , and the index of M j in D nj ,kj , -indexes to the neighbors of N j in G (for each side of M j , the index of the corresponding neighbor and side).

In particular the number of edges in the graph G is bounded by the total number of sides in the M j . We first need an hypothesis ensuring that the additive part of the entropy matches the entropy αn of the class to which M belongs.

Hypothesis 1. The decomposition is additive in the size parameter (elementary cells are not shared):

n 1 + . . . + n p = n + O n lg n .
As expressed by the term O( n lg n ) we allow a negligible number of elementary cells to be shared between tiny pieces.

Observe that we do not require the class D m = k D m,k to have the same entropy as C m : in particular in our two main examples below we will have ||D m || ∼ α ′ m with α ′ > α. As a consequence, in order for the representation to be compact we need a second hypothesis on the number of sides.

Hypothesis 2. The decomposition involves a sub-linear number of sides:

k 1 + . . . + k p = O n lg n .
This second hypothesis implies that the whole cost of storing indexes to all the M i remains of order αn. Next hypothesis ensures that the elements of D, needed in the decomposition, fit in a small catalog. Hypothesis 3. In the decomposition each M j can be taken of size between c 3 lg n and c lg n, where c < 1/α ′ , with α ′ the entropy per size unit of D.

Indeed assume that the indexes are pointing into a table A, containing the explicit representations of all elements of D m for m ≤ c lg n for some constant c (where c depends on the cardinality of D). If the constant c is chosen small enough, the number of entries in the table is sub-linear: indeed ||D m || = α ′ m ≤ cα ′ lg n, so with c < 1/α ′ , the number of entries in the table is O(n cα ′ ). The total storage cost of Table A then remains sub-linear as long as the information for each piece is polynomial in its size m = O(log n). In particular, explicit answers to local queries (as local adjacency or degree queries on elementary cells) can be stored using auxiliary information without affecting significantly the overall size of the representation.

Compactness

Hypothesis 2 above ensures that the graph G has O(n/ lg n) edges, and Hypothesis 3 that it has O(n/ lg n) vertices. This is already enough to obtain compactness. Proof. Recall that each vertex N j of G contains: n j , k j and the index of M j in D nj ,kj , as well as indexes to the neighbors of N j in G. As n j and k j are smaller than c lg n and Kc lg n respectively, we can store them in 2 lg lg n + O(1) bits.

When summing over the O(n/ lg n) vertices of G we get a O n lg lg n lg n bits cost. Using Equation ( 1) the index of M j requires αn j + β k j lg n j + O(lg n j ) bits. Summing over all M j yields a global cost of

j D nj ,kj ≤ α j n j + β( j k j ) lg(max j n j ) + O   j lg n j   ≤ αn + O( αn lg n ) + βO( n lg n ) lg(c lg n) + n lg n O(lg lg n)
Using Hypotheses 1 and 2, the cost of all indices to Table A thus reduces to αn + O n lg lg n lg n bits. Since there are O(n/ lg n) vertices in G, the index of a neighbor uses lg n + O(1) bits. Vertex N j has O(k j ) neighbors, thus the total cost for storing indexes to the neighbors is (lg

n + O(1)) • j k j = O(n).
Summing all these components yields the claimed complexity.

Succinctness

In the proof of Lemma 2 the linear part of the storage came from two kinds of contributions: the contribution of indexes in the catalog which is dominated by the entropy αn, and the contribution of the neighboring relations in the graph G. In this section, the cost of this second part is reduced to be sub-linear.

The graph G is partitioned into small pieces gathering O(lg n) tiny pieces. More precisely we assume that we are able to construct a graph G ′ obtained by merging several vertices of G in a vertex of G ′ and linking two such vertices if there is an edge in G between two of their elements. The vertex set of

G ′ is {N ′ 1 , N ′ 2 , . . . N ′ p ′ } and we denote |N ′ i | the number of vertices of G that have been merged to obtain N ′ i and deg ′ (N ′ i ) the degree of N ′ i in G ′ . A vertex N ′ i of G ′ then consists of the following information: -|N ′ i | and deg ′ (N ′ i ) -the information for all the vertices N j ∈ N ′ i , stored in a single memory zone. -indexes to neighbors of N ′ i in G ′ .
The graph G ′ has moreover to satisfy the following hypotheses.

Hypothesis 4. The number of tiny pieces gathered in each small piece N

′ i satisfies: 1 3 lg n ≤ |N ′ i | ≤ lg n.
The number of edges from a given vertex of G ′ can be bounded by summing over its elements:

deg ′ (N ′ i ) ≤ Nj ∈N ′ i deg(N j ) = Nj ∈N ′ i k j ≤ |N ′ i |Kc lg n = O(lg 2 n)
(where K is a constant describing the size of the boundary of tiny pieces, as introduced at Equation ( 1)). But we need a stronger hypothesis on the total number of edges of G ′ . Hypothesis 5. The number of edges of G ′ is linear in its number of vertices:

deg ′ (N ′ 1 ) + . . . + deg ′ (N ′ p ′ ) = O n lg 2 n .
Observe that Hypothesis 4 and the way we gather the nodes of graph G guarantee that the number of nodes of G ′ is at most O( n lg 2 n ). Next Lemma ensures that the storage cost for graph G is asymptotically negligible. Proof. First we notice that in the above representation of G (Lemma 2), a vertex N j uses O(lg 2 n) bits (O(lg n) bits for the index of M j in the relevant catalog and O(lg n) for each of its, at most, Kc lg n neighbors) which gives easily a bound of O(lg 3 n) for the memory needed by all vertices of G that merge in some N ′ i . Hence a local reference to memory addresses relative to some known N ′ i requires lg lg n + O(1) bits. Let us now return to the information stored in a vertex N j ∈ N ′ i of G. To refer to a neighbor N l of N j , instead of using an address in the whole memory devoted to G, we refer first to the vertex N ′ k ∋ N l and then give the address of N l in the memory zone devoted to elements of N ′ k . Referring to N ′ k is done indirectly by giving its index in the array of the, at most, O(lg 2 n) neighbors of N ′ i . Thus a reference to a neighbor N l of N j costs O(lg lg n) bits. The analysis of the size of G is similar to the argument used in Lemma 2: here the cost of a reference to a neighbor does go from O(lg n) down to O(lg lg n) which yields the claimed complexity. The additional cost for G ′ is sublinear since it has O( n lg 2 n ) vertices by Hypothesis 4 and edges by Hypothesis 5 and each costs O(lg n) bits.

Local planarity and mesh connectivity

The above framework easily applies to trees: a tree with n vertices can be recursively decomposed into tiny trees of logarithmic size, with sides consisting of edges connecting nodes of different tiny trees.

More interestingly Hypotheses 1, 2, 3, 4 and 5 are naturally satisfied when dealing with mesh connectivity (that is, for maps on surfaces). Following for instance [START_REF] Castelli Aleardi | Succinct representation of triangulations with a boundary[END_REF], a triangulation M with n faces can be partitioned into tiny regions by decomposing an arbitrary dual spanning tree into tiny trees (that is, a spanning tree of the dual graph, connecting all faces across edges): upon reforming a (local) planar triangulation from each tiny tree, a decomposition (M 1 , . . . , M p ) is obtained, such that: -each tiny triangulation contains between 1 12 lg n and 1 4 lg n triangles (that is, c = 1/4); -each triangle belongs to exactly one tiny triangulations; -boundary edges are regrouped into sides (sequences of edges separating it from the same tiny triangulation). The bound on the number of edges of the graph G that describes adjacency relations between sides of tiny triangulations follows from Euler's relation.

This direct application of the framework to triangulations using an arbitrary spanning tree forces us, as explained in [START_REF] Castelli Aleardi | Succinct representation of triangulations with a boundary[END_REF], to consider the catalog D m,k of all planar triangulations with m edges and one boundary cycle, which is divided into k sides. The entropy of this class of triangulation with a boundary is however α = 2.17 bits per face (plus a βk lg m term to take into account the number of sides into which the boundary is divided). As a consequence, the additive part of the entropy leads to a representation which is compact, but succinct only for class of triangulations with a boundary (recall that the class of triangulations of the sphere has only entropy 1.62 bits per triangle).

In summary, one can expect the general framework to yield easily compact representations for mesh connectivity with bounded face degrees. However, as we shall see, more care is needed to choose the decomposition in order to produce a succinct representation.

Local adjacency queries in O(1) time

It still remains to observe that the multi-level structure (described by graphs G and G ′ , together with the information associated with tiny pieces M j ), does allow to perform efficiently some local adjacency queries (neighboring queries on elementary cells). Proof. The idea is that elementary cells (faces, vertices, edges) are shared by at most one or two adjacent tiny pieces (because of the definition of graph G), except for a small set of multiple cells (shared by an arbitrary number of tiny pieces). The planarity of graph G ensures that the number of multiple cells is O( n lg n ), hence adjacency queries involving multiple cells can be answered with an additional information, which requires in overall a negligible amount of extra storage. Intuitively, local queries involving only a tiny piece M i are answered looking at the information contained in the corresponding explicit representation (stored in Table A), allowing O(1) time navigation. Adjacency queries concerning elementary cells incident to the boundary of a tiny piece M j , rely instead on the information in graphs G and possibly G ′ . Some care must be taken to deal with the fact that a given cell at the meeting point between a lot of tiny pieces can have a non constant number of representations: however the number of such special cells is negligible and they can be detected at the G ′ level.

Attaching external data to elementary cells

Since our framework is designed to represent geometric objects (graphs, surfaces meshes, ...) it should be natural to allow dealing with other type of information2 , such as vertex coordinates or other properties associated to elementary cells (color of faces, normals, ...). We can solve this problem by enriching our representation adding auxiliary information to the nodes of graph G. More precisely, we can add to a node N j the list of geometric data associated to cells lying in the tiny piece M j . This list contains the data associated to the internal cells of M j and a selection of cells lying on its boundary, in such a way that boundary cells shared by two adjacent tiny pieces (not multiple cells) are stored only once. Multiple cells (shared by several tiny pieces) can have multiple copies: this does not affect the size of our representation, since their number is negligible. It suffices to list the set of multiple cells shared by tiny pieces: we distinguish between multiple cells relative to a same node N ′ i and those which are shared by tiny pieces corresponding to different nodes of G ′ . There are very few cells of second type: since their number is Θ( n lg 2 n ) storing their external data requires negligible auxiliary space. Concerning cells of first type, because our regrouping of nodes of G, the number of such cells relative to a node N ′ i is at most O(lg 2 n) (hence a reference costs O(lg lg n) bits): then it suffices to store, for each node N ′ i , the list of geometric data of a selection of these multiple cells, such that external data are stored only once. The same argument used before for the succinctness of the representation of G allows to guarantee the the overall number of copies concerning multiple cells does not affect the storage requirements of our encoding.

Construction of the representation in O(n) time

For concluding the presentation of our general framework we have to mention that we need further assumptions to allow O(n) time construction. Given an object M ∈ C n of size n, we assume we are able to compute a binary encoding for M of length at most O(lg |C n |) (in O(n) time). We need this assumption to guarantee that all references used in our representation are of size Θ(lg n): recall that we adopted the word -RAM model, where words of size O(lg n) can be handled in O(1) time.

Representing 3-connected planar graphs

In this section section we describe a particular catalog of tiny quadrangulations and an algorithm to decompose any irreducible quadrangulations into tiny regions taken from this catalog. This catalog satisfies Equation 1 so that the framework yields a succinct representation. Since irreducible quadrangulations are just another representation of 3-connected planar graphs, the result holds for these maps as well.

Preliminaries on 3-connected graphs, quadrangulations and trees

Plane trees are planar maps with only one face, the outer one. In other terms, plane trees only differ from the classical ordered trees in the fact that they are not rooted. As done in [START_REF] Fusy | Dissections and trees, with applications to optimal mesh encoding and to random sampling[END_REF] we consider a special class of plane trees, binary trees where each vertex has 3 neighbors (and hence 2 sons if rooted). A vertex is a leaf if it has degree 1, otherwise it is an internal node.

Edges incident to leaves are called stems, remaining edges are called inner edges. A quadrangulation is a planar map having all its faces of degree 4. A dissection of the hexagon by quadrangular faces is a planar map whose outer face has degree 6 and inner faces have degree 4. A quadrangulation or dissection of the hexagon by quadrangular faces is said irreducible if it has no separating 4-cycle (we also call them irreducible dissections).

The following construction is more or less a folklore variation on the standard duality construction (also known as the Tutte's bijection, see [START_REF] Mullin | The enumeration of c-nets via quadrangulations[END_REF]) for planar maps: given a 3-connected planar map M , color its vertices in black and put a white vertex in the middle of each face and triangulate each face from this white vertex. The resulting new edges form a quadrangulation Q (each face is made of the two triangles incident to an edge of M ). It is not difficult to check that the 3-connectedness of M is equivalent to the irreducibility of Q. Finally let us observe that it is possible to associate a rooted dissection d of the hexagon to a rooted irreducible quadrangulation Q by deleting the root edge.

Intuitively, a quadrangulation Q can be viewed as an implicit representation of a planar map, induced with a bicoloration of its vertices: white (resp. black) vertices of Q stand for faces (resp. vertices) of the original (resp. dual) map (see Fig. 1). More precisely, testing adjacency relations between vertices and faces in map M corresponds to answering neighboring queries on vertices incident to the same face in the quadrangulation Q. It will prove convenient to describe our construction in terms of quadrangulations.

How does our framework apply

Our decomposition strategy will take advantage of the fact that irreducible dissections admit a special class of canonical spanning trees, described in [10]: Proposition 5. There exists a bijection between the class of binary trees on n internal nodes and the class of irreducible dissections with n internal vertices, which can be computed in O(n) time.

Let us suppose to have an irreducible dissection Q of the hexagon with quadrangular faces. Following the traversal strategy explained in [START_REF] Fusy | Dissections and trees, with applications to optimal mesh encoding and to random sampling[END_REF], it is possible to perform an opening algorithm on Q which returns a binary tree: the result is a vertex spanning tree of Q, whose complete closure [10, Lemma 2] is exactly the original dissection of the hexagon (corresponding to a 3-connected planar graph). More precisely it is a binary tree B on n nodes having n + 2 stems and (n -1) inner edges (the correspondence is illustrated in Figure 1).

Let us recall a previous result concerning tree decompositions, stated in the following Lemma [START_REF] Munro | Representing dynamic binary trees succintly[END_REF]: Lemma 6. Given a binary tree B on n nodes and a positive integer parameter δ, we can produce in linear time a partition of B into a family of sub-trees B j , whose sizes satisfy δ ≤ B j ≤ 3δ.

Applying several times the algorithm above, we obtain a partition of B into small binary trees having between 1 3 lg 2 n and lg 2 n nodes, which are then decomposed into tiny binary trees having between 1 30 lg n and 1 10 lg n nodes. Such a decomposition forms a partition of the edges of B (which are edges of the original quadrangulation). Let us observe that only nodes, those which are roots of tiny (resp. small) trees, are shared by different tiny (resp. small) trees: each of these nodes (having degree d) is split into a degree d -1 root of one tree (descendent tree) and a leaf of another tree (ancestor tree). The way we have partitioned B guarantees that number of tiny (resp. small) trees is Θ( n lg n ) (resp. Θ( n lg 2 n )).

Decomposition into tiny quadrangulations

The aim of this section is to describe a canonical way of obtaining a decomposition {M 1 , . . . , M p } of Q, starting from the decomposition of the vertex spanning tree B. Here we suppose we are given one tiny tree, denoted T B j , having n j ≤ 1 10 lg n nodes and w j false stems, obtained by decomposing B: we are going to show how to produce a tiny quadrangular map of size Θ(lg n) from T B j . A tiny tree T B j has n j nodes and n j + 2 stems: we now distinguish two kinds of leaves. Firstly there may exist some leaves which were already existing, as leaves, in the original tree B. On the other hand, there may exist some new leaves which correspond to internal nodes of B, before performing the decomposition into tiny trees: their incident edges are now called false stems. Recall that tiny trees are rooted (roots are shared by different tiny trees), and the number of false stems in a tiny tree is not fixed and it ranges in 0 . . . n j + 2, depending on the way B has been partitioned.

Local closure

Now it suffices to apply a "local closure" algorithm, inspired by the one introduced in [START_REF] Fusy | Dissections and trees, with applications to optimal mesh encoding and to random sampling[END_REF], whose main steps are listed below (recall that in the original algorithm of [START_REF] Fusy | Dissections and trees, with applications to optimal mesh encoding and to random sampling[END_REF], there was no distinction between true and false stems).

Let us perform a counterclockwise (ccw) traversal of the contour of T B j , starting from its root and walking along its edges (inner edges, stems and false edges).

-When traversing a true stem, which is preceded by 3 internal nodes (and not stems), its local closure consists in linking its incident node, with the preceding third node (on the boundary of the outer face) to create a quadrangular face (a white face in Figure 2).

-When traversing a (true) stem s, not preceded by 3 true nodes (original nodes existing in T B j ), its local closure consists in attaching a dummy quadrangular face (a grey face in Fig. 2) to the boundary of T Q j , in such a way that the dummy face is then incident to the stem s and does not enclose a false stem nor a dummy edge (i.e. an edge incident to a dummy face) previously added. Similarly, vertices incident to dummy faces, and not existing in the tiny tree, are called dummy vertices. Let us observe that we do not perform the merging of false stems (drawn with small circles in Figure 2).

In this way we produce a planar map whose internal faces are all quadrangles, and having an outer face of arbitrary size: inner edges (in the tree) may now be incident twice to the outer face.

Catalog of micro quadrangulations

The planar connected maps obtained in this way are also called tiny quadrangulations (the result of the procedure above is shown in Figure 2). Here we consider the catalog D = {D p,k,w } containing all different quadrangulations obtained applying the strategy above. More precisely, an object M j of {D p,k,w } is a tiny quadrangulation T Q obtained via our local closure from a tiny tree T B having p nodes, p + 2 stems and w j false stems (the size parameter is the number p of nodes in the tree). Moreover T Q is induced with a partition of its boundary edges into k sides. One can easily see that given a tiny binary tree with p nodes, the corresponding tiny quadrangulation has a boundary of size at most 4p + 6. 3 . We can then state the following bound on the size of catalog D:

lg |D p,k,w | ≤ lg 2 2p • 4p + 6 k • p + 2 w ≈ 2p + k lg p + w lg p + O(k),
(since there are p+2 w ways of distributing false stems, and 4p+6 k ways of partitioning boundary edges into sides; we have also w ≤ k). The storage of elements of D (with their explicit representations) requires a negligible amount of space: recall that p, the number of nodes in a tiny tree, is at most 1 10 lg n.

Distribution of false stems

Once the initial spanning tree B has been decomposed, we have to specify a rule for assigning (true) stems incident to nodes shared by tiny trees. We proceed as follows, assuming that v is shared by two tiny trees T B j ′ and T B j ′′ , and denoting the possibly incident stem by s (see Pictures in Fig. 3):

3 Concerning inner edges, doubly incident to the outer face, their number is p-1, hence their contribution to the boundary size is at most 2(mp -1). On the other hand, the contribution of dummy faces is maximum when a dummy face is produced by a true stem immediately preceded by a false stem: as there are p + 2 stems, there may be at most ⌈ p+2 2 ⌉ dummy faces, each contributing for 4 edges. Finally the size of the boundary of a tiny quadrangulation is bounded by 2(p -1) + 4( p+2 2 + 1) = 4p + 6.

-if there exists in the descendant tree B an inner edge e incident to v to the left of s, then we attach the stem s to the tiny sub-tree T B j ′′ having v as root and containing e;

-otherwise s is the leftmost sibling of node v in B, and we do attach s to the ancestor tree T B j ′ .

It is easy to observe that all the faces of the initial quadrangulation have been assigned to exactly one tiny quadrangulation, as they are incident each to one true stem.

Verification of the Hypotheses

Lemma 7. Given a quadrangulation Q with n vertices, our new splitting strategy produces a decomposition into tiny quadrangulations {T Q 1 , . . . , T Q p } satisfying Hypotheses 1, 2, 3, 4 and 5, and hence yields a succinct representation of Q requiring asymptotically 2n + o(n) bits.

Proof. The additivity hypothesis holds, since (true) nodes in tiny quadrangulations (nodes of the tiny spanning tree) are not shared by tiny quadrangulations. The quadrangulation Q is decomposed into tiny quadrangulations T Q j each containing between 1 30 lg n and 1 10 lg n nodes (nodes of the corresponding tiny vertex spanning tree): here the constant c introduced in Section 2 is set to

1 10
. The graph G used to describe adjacency relations between tiny quadrangulations is a planar map (each tiny quadrangulation is a connected planar map, whose edges may be incident twice to the outer face, and then doubly counted as boundary edges) having faces of degree at least 3 (for example, a degree 2 face incident to multiple edges can be contracted, observing that the corresponding sides are consecutive and shared by the same two tiny quadrangulations). Hence Euler's relation ensures that the number of arcs of G (and hence the number of sides) is O( n lg n ). Hypotheses 1, 2, 3 5 and 4 are satisfied by {T Q 1 , . . . , T Q p }, hence Lemma 3 yields a succinct representation for the class of quadrangulations achieving the optimal asymptotic bound of 2 bits per vertex. A tiny colored quadrangulation is completely specified by: a Dyck word of length 2n j (for the binary spanning tree), a binary word of length n j + 2 and weight w j (describing false stems) and a binary word of length 4n j + 6 and weight k j (describing the partition of boundary edges of T Q j into sides). Hence T Q j can be encoded by a reference to an element in D, whose cost is 2n j + w j lg(n j + 2) + k j lg(4n j + 6) ≤ 2n j + βk j (lg n j + O( 1)) (as w j ≤ k j ). The constant c can be chosen so that the Table A containing the explicit representations of the elements of D, requires o(n) bits (recall that n j ≤ 1 10 lg n).

Representing 3-connected planar graphs

Given a 3-connected graph with e edges, we first design a succinct representation of the associated quadrangulation. Since the corresponding vertex spanning tree has e -5 inner nodes (vertices of the primal and dual graph) our representation requires asymptotically 2(e-5)+o(e) = 2e+o(e) bits, according to Lemma 7. It suffices to observe that testing adjacency between two vertices (resp. two faces) in a 3-connected graph, is equivalent to checking if two black (resp. white) nodes are opposite in the same quadrangular face, in the associated quadrangular map Q. This operation can be efficiently performed in O(1) time with a slight modification of the standard adjacency queries considered in Lemma 4 (see Section 5 for more details).

Unique representations for vertices

As already observed, a number of elementary cells (multiple cells) are shared by several tiny pieces. One major problem to solve concerns the representation of vertices, which is not unique, as they can belong to more than one piece. One possible solution consists in exploiting the correspondence between vertices in the quadrangulation and nodes in the spanning tree. It simply suffices to associate to each vertex in Q the corresponding node in the tree B.

Then inner nodes in a tiny tree T B j are uniquely specified. Remaining vertices, multiple vertices shared by tiny pieces, can be uniquely identified, saying that their canonical representative is the corresponding node in an adjacent tiny piece (in particular, for a multiple node shared by two tiny trees, its canonical representative is the leaf node in the ancestor tree).

Figure 5: These two Pictures illustrate the adjacency relations between tiny quadrangulations: since edges are allowed to be incident twice to the outer face, two tiny quadrangulations T Q j ′ and T Q j ′′ may be not adjacent even if "sharing" an edge e.

Representing planar triangulations

Preliminaries on planar triangulations and trees

As done for 3-connected graphs, we take advantage of a recent bijection between planar triangulations and trees introduced in [START_REF] Poulalhon | Optimal coding and sampling of triangulations[END_REF]. Proposition 8. There exists a 2n-to-2 correspondence between the class of rooted trees with n nodes having 2 leaves per node, and the class of rooted planar triangulations with n + 2 vertices. This correspondence relies on an opening/closure algorithm which computes a special vertex spanning tree (with two leaves per node) on n nodes from a triangulation T , induced with its minimal realizer.

Decomposition of the graph

Here we suppose we are given a rooted triangulation T with n + 2 vertices and the corresponding vertex spanning tree B on n nodes, whose complete closure is the initial triangulation (according to the closure/opening algorithm introduced in [START_REF] Poulalhon | Optimal coding and sampling of triangulations[END_REF]). Since there are no restrictions on the tree B (it is just an ordered tree, with two leaves per node), we cannot in general decompose B to get a partition into sub-trees as done for binary trees. Thus we describe below a different decomposition where few nodes can be shared by several sub-trees, but edges appears only once. First we distinguish in a subtree three kind of nodes: the leaves, the root and the internal nodes. Now we say that a family of subtree is a covering of B if -(i) each node of B appears either in only one subtree as an internal node, either in several subtrees, in one subtree as a leave and others as the root.

-(ii) each edge of B appears in exactly one subtree. -(iii) the children of the root r in one subtree correspond to consecutive children of r as a node of B.

Then, the following Lemma controls the size of the subtrees. This Lemma is similar to the one designed for ordered trees [START_REF] Geary | Succint ordinal trees with levelancestor queries[END_REF], whose decomposition provides a covering of the nodes but not a partition of the edges (some edges may not appear in any subtree) and for which condition (iii) is also not guaranteed.

Lemma 9. Given a tree B on n nodes and δ ≥ 2, we can compute a family of sub-trees that is a covering of B. Their sizes satisfy B j ≤ 3δ -2 (and B j ≥ δ, if the B j does not contain the root of B). Such a decomposition can be computed in linear time.

Proof. The following algorithm will construct the covering within the claimed complexity bound. We traverse B in postfix order and maintain a subtree B of B which is the not yet decomposed part of B. In a node r we perform the following operations depending on the size of the subtree of B rooted at r : -if the size is smaller than M then the size is returned to the parent of r (thus the parent is able to evaluate the size of its subtree) -if the size is between M and 3M -2, the subtree rooted at r is returned as a subtree of the covering, in B, r is replaced by a single leaf and 1 is returned to the parent as size of the subtree.

-if the size is bigger than 3M -2, r has κ children s 1 , s 2 . . . s k (κ ≥ 4) whose size of subtree are σ 1 , σ 2 . . . σ k . For all i we have 1 ≤ σ i < M , we consider the smallest value j such that τ = j i=1 σ i ≥ M , since j-1 i=1 σ i ≤ M -1 and σ j ≤ M -1 we have τ ≤ 2M -2. Then r, σ 1 , σ 2 . . . σ j is returned as a subtree of the covering (of size ≤ 2M -1), σ 1 , σ 2 . . . σ j are removed as children of r in B. The process is continued to gather children of r, at the last step we may finish with s l . . . s k with a size k i=l σ i < M , then this children are grouped with those of the preceding step giving a maximal size of 2M -2 + M -1 + 1 = 3M -2 for this subtree. Finally, r is replaced by a single leaf in B and 1 is returned to the parent as size of the subtree.

Applying several times Lemma 9 to B, we obtain a family of small subtrees covering B of size Θ(lg 2 n), which are then decomposed into tiny sub-trees having Θ(lg n) nodes. This family of sub-trees forms a cover of the nodes of B such that two sub-trees can intersect only at their root.

Tiny trees and tiny triangulations

As done for quadrangulations, it is possible to define a local closure algorithm (inspired by the one described in [START_REF] Poulalhon | Optimal coding and sampling of triangulations[END_REF]), providing a correspondence between tiny trees and tiny triangulations. Firstly, if a tiny tree T B j has an inner node v of degree 3, which appears as root of one (or more) different tiny tree T B j ′ (neighbor of T B j ), we set v as false degree 3 inner node (in this case v had degree more than 3 in B).

Distribution of stems Observe that tiny trees could have less than two leaves per node. In order to make a tiny tree belong to the same class as B, we perform some modifications on it. Original stems in B are duplicated and distributed between tiny trees T B j so that each node has two leaves. The strategy is similar to the one adopted in Section 3 for quadrangulations: we have only to take care that micro trees in this case are not binary trees, and each node must have exactly two incident stems. Duplicated stems, called false stems, are assigned to the tiny trees sharing a same node v, in such a way that the cyclic order of neighbors around v is respected. Observe that false inner nodes are incident to at least one false stem, at the exception of the root node of a tiny tree (see Figure 9). It is straightforward to observe that the number of false degree 3 inner nodes and false (duplicated) stems is in overall O( n lg n ).

Closure of a micro tree and catalog of micro triangulations

Our local closure of a tiny tree T B j consists in performing a ccw traversal along its edges (starting from its root, in ccw order). As done in Section 3, we add a (true or dummy) triangular face by performing the merging of true stems: this depends on the distribution of false stems and false inner nodes. More precisely, we merge a stem in the following manner:

-if a true stem s is preceded by 2 (true) inner nodes, we link its incident node to the second preceding node to create a triangular face; -otherwise, if s is preceded (on the boundary of the outer face) by a vertex v which is not an inner node we add a dummy triangular face incident to s and v (a grey face in Figure 8). The planar connected maps T T j we obtain in this way (whose internal faces are all triangles, and with an outer face of arbitrary size) are called tiny triangulations. Proof. Our arguments rely on the same remarks used in the proof of Lemma 7. The additivity Hypothesis holds, since tiny triangulations only share duplicated nodes (roots of tiny trees), whose number is O( n lg n ). Here an object M j = T T j is a tiny triangulation: T T j is obtained via our local closure from a tiny tree T B j having n j nodes, 2n j stems and w j false stems; its boundary edges are partitioned into k j sides. Hence a tiny triangulation is described by: a binary word of length 4n j -2 and weight n j -1 (there are about 2 3.24nj such words, see [START_REF] Poulalhon | Optimal coding and sampling of triangulations[END_REF]), a binary word of length 2n j and weight w j (for false stems) and a binary word of length 6n j -2 and weight k j (a tiny triangulation has at most 6n j -2 boundary edges). Again the constant c can be chosen so that Catalog D requires an asymptotic negligible amount of space.

Verification of the Hypotheses

Efficient local queries

In this section we discuss the implementation of a few natural supplementary queries that can easily be supported by our structures. A vertex in a tiny quadrangulation T Q j can be specified by a triple (N ′ i , a, v): where N ′ i is a node of map G ′ , corresponding to the small piece SQ i to which it belongs, a is a local pointer to the zone of memory related to node the N j , and v is the index of Figure 9: In these Pictures is depicted our strategy for constructing a decomposition of the original triangulation T into tiny triangulations. At first the vertex spanning tree of T is decomposed into tiny trees. We perform our local closure algorithm on tiny trees, producing tiny triangulations. Each tiny triangulation is provided with a partition into sides of its boundary edges describing neighboring relations.

the vertex in the explicit representation, stored in Table A, corresponding to T Q j . As already observed in [START_REF] Castelli Aleardi | Succinct representation of triangulations with a boundary[END_REF], in our encoding vertices may be not uniquely represented, because they are shared by different tiny pieces. Analogously, representing (quadrangular or triangular) faces is done specifying a triple (N ′ i , a, f ): their representation is uniquely defined, as faces are not shared by tiny pieces.

Adjacency queries between faces and vertices

Next Lemma provides an useful tool for local navigation between faces of adjacent tiny pieces: its proof relies on arguments similar to the ones detailed in [START_REF] Castelli Aleardi | Succinct representation of triangulations with a boundary[END_REF], which are still valid for arbitrary tiny pieces (having faces of arbitrary constant degree).

Lemma 11. Given an object M and its decomposition into tiny (and small) pieces [(M 1 , . . . , M p ); G; G ′ ], it is possible to answer in constant time the following local queries:

-Neighbor(f, e): given a face f and an incident edge e, it returns the face f ′ adjacent to f containing e.

-Adjacent(v, w): says if two vertices v and w are adjacent.

Unique representation for vertices

It is possible to avoid the problem of having multiple representations of vertices, by adopting a local labelling scheme and distinguishing vertices into 3 categories: vertices internal to a tiny piece, vertices shared by more than 2 tiny pieces, and vertices shared by more than 2 small pieces. As observed in Section 3.

Local adjacency queries on the quadrangulation

Concerning the local navigation in the quadrangulation, our representation allows to perform in O(1) time the following operation (which provides efficient navigation in the original 3-connected graph, as discussed in Section 3.6).

Lemma 13. In a quadrangulation Q it is possible to answer in O(1) time the following neighboring query:

-Opposite(v, w): returns true if two vertices v and w are opposite and incident to the same quadrangular face in Q.

Proof. The validity of our arguments relies on the following properties that hold for 3-connected planar graphs and corresponding quadrangular irreducible dissections.

-The vertex spanning tree introduced in [10] is a binary tree, implying that the degree of nodes and the number of stems per node is bounded and constant.

-Every quadrangular face in the decomposition of Q belongs exactly to one tiny quadrangulation. Moreover every node v is incident to at most two dummy faces in the same tiny quadrangulation: for nodes with two stems, we observe that each dummy face is created by merging one of its stems; for nodes with one stem (possibly producing one dummy face), only one more dummy face may exist, possibly incident to the descendant node in the tree (see node w in Figure 10).

-For each pair of vertices v and w there is at most one quadrangular face (if it exists) containing the two vertices and for which v and w are opposite (because the quadrangulation Q has no separating 4-cycle).

Let q be the quadrangular face possibly incident v and w, let us call v ′ , v ′′ , . . . (resp. w ′ , w ′′ , . . .) their copies, and let T Q j , T Q j ′ , T Q j ′′ , . . . denote the tiny quadrangulations containing them. We may suppose, without loss of generality, that v precedes w on the boundary of the spanning tree B, which is ccw oriented. For the sake of clarity, let us assume that v and w are not multiple nodes, roots of different tiny trees (as in Figure 10). If v and w are vertices lying in the same tiny quadrangulation (hence j = j ′ ) we can answer by simply looking at the explicit representation stored in Table A: as v and w are at distance 2 in T Q j , answering this query requires storing o(n) extra bits. If the vertices belong to different tiny quadrangulations (not necessarily adjacent tiny quadrangulations) we retrieve at first their canonical representatives: if Canonical(v) and Canonical(w) belong to the same tiny quadrangulation, we are in the previous case and we proceed as before. Otherwise we proceed as follows, assuming that v is preceding w in ccw order. If v and w would be opposite and incident to a face q, then q should Figure 10: In these Pictures is depicted the case of two vertices v and w (small blue circles), opposite and incident to the same quadrangular face q 1 (last Picture): v and w are multiple vertices (shared by different tiny pieces), but not multiple nodes (as they do not belong to different tiny trees). Multiple nodes are represented in the first Picture with small red circles.

belong to the same tiny quadrangulation containing w and be incident to one of the edges of T B j ′ (inner edge or stem) which is incident to w. Since the degree of nodes in B is bounded we know that there exist at most 2 quadrangular faces satisfying the last condition, say q 1 and q 2 (grey faces in Figure 10). Let us now retrieve the two vertices v ′′ and x ′′ , opposite to w, which are incident to q 1 and q 2 (using information stored in Table A). Finally it suffices to test whether the Canonical(v ′′ ) and Canonical(x ′′ ) do coincide with v (canonical representative of the copies of v). For concluding, we observe that the case where v (or w) is a multiple node can be dealt in a similar manner: we can repeat the steps above a constant number of times, since each multiple node is contained in at most two different tiny trees.

Concluding remarks

We have presented a general framework for describing succinct representations of planar maps. In the particular case of 3-connected graphs and triangulations, we propose moreover canonical decompositions which, combined with the general framework, yield encodings that achieve asymptotically the informationtheoretic lower bound for the storage, while supporting efficiently standard local navigation operations. The generality of our arguments suggests that our framework could apply to other popular encoding schemes, getting compact representations of other classes of planar graphs. This should take advantage of the similarities between explicit spanning tree coding [START_REF] Keeler | Short encodings of planar graphs and maps[END_REF][START_REF] Turan | Succinct representations of graphs[END_REF] and regiongrowing approaches [START_REF] Rossignac | Edgebreaker: Connectivity compression for triangle meshes[END_REF][START_REF] Touma | Triangle mesh compression[END_REF] as discussed in [START_REF] Isenburg | Graph Coding and Connectivity Compression[END_REF]. One interesting open problem is to extend optimal encodings [START_REF] Poulalhon | Optimal coding and sampling of triangulations[END_REF] and compact representations of graphs [START_REF] -N Chuang | Compact encodings of planar graphs via canonical orderings and multiple parentheses[END_REF][START_REF] Chiang | Orderly spanning trees with applications to graph encoding and graph drawing[END_REF] to the case of higher genus triangulated surfaces. Although our results here are mainly theoretical (as in the case of previous works on compact representations [START_REF] Chiang | Orderly spanning trees with applications to graph encoding and graph drawing[END_REF][START_REF] -N Chuang | Compact encodings of planar graphs via canonical orderings and multiple parentheses[END_REF][START_REF] Munro | Succint representation of balanced parantheses and static trees[END_REF]) this work has been a good source of inspiration for a practical solution [START_REF] Castelli Aleardi | 2D Triangulation Representation using Stable Catalogs[END_REF]. The main idea is that n could be considered more as a constant than a parameter: so our aim is to design a hierarchical structure based on a splitting in tiny and small triangulations whose sizes are limited by finely tuned constants.

  |C n |. The entropy ||C n ||, defined by ||C n || := lg |C n | with lg(x) = ⌈log 2 (x+1)⌉, measures the diversity of the class. A class has linear entropy if there exists a constant α such that ||C n || = αn + o(n), when n goes to infinity.

Lemma 2 .

 2 Under Hypotheses 1, 2, and 3 the storage of the graph G requires O(n) bits.

Lemma 3 .

 3 Under Hypotheses 1, 2, 3, 4 and 5 the graph G can be stored using αn + O n lg lg n lg n bits.

Lemma 4 .

 4 Let us consider an object M which is provided with a decomposition [(M 1 , . . . , M p ); G; G ′ ] as defined above. If each of the tiny pieces M j is a planar connected map having all faces of constant degree and a boundary of arbitrary linear size O(n j ), then it is possible to answer in O(1) time whether two elements of M (vertices or faces) are adjacent or not.

Figure 1 :

 1 Figure 1: First Pictures describe the closure defining the correspondence between plane rooted binary trees and irreducible dissections of the hexagon. The dissection and the corresponding 3-connected graph are also shown. Black circles (resp. white circles) represent vertices of the primal (dual) graph.

Figure 2 :

 2 Figure 2: Our local closure. The result of the closure operation does depend on the distribution of false stems. In our example, the binary tree has 11 inner vertices, 11 + 2 leaves (true and false stems, including the stem incident to the root), and can be optimally encoded by the binary word of length 2 • 11: 1101001011001001011000; while the corresponding false stems distribution is defined by the bit-vector of length 13 and weight 4: 0000100001101.

Figure 3 :

 3 Figure 3: These Pictures explain how distributing stems and (dummy) faces between tiny quadrangulations sharing a node v (a multiple node, represented with a small circle).

Figure 4 :

 4 Figure 4: This Figure illustrates our multi-level hierarchical representation of a quadrangulation. The decomposition of B provides, via our local closure, a partition of Q, into tiny quadrangulations. Neighboring relations between tiny quadrangulations are described by a planar map G.

Figure 6 :

 6 Figure 6: Vertex spanning tree bijection between rooted planar triangulations and rooted trees with 2 leaves per node.

Figure 7 :

 7 Figure 7: This images show the result of our decomposition strategy for trees (Lemma 9) on an ordered tree with parameter δ = 3.

Figure 8 :

 8 Figure 8: This Figure shows a tiny triangulation obtained via our local closure from a tiny tree T B.In our example we start with a tiny tree having 5 nodes and 10 leaves: there are 3 false stems (small circles) and 3 false inner nodes (including the root). The stems distribution is described by a binary word of length 10 and weight 3: 0010100001.

Lemma 10 .

 10 Given a planar triangulation T with n + 2 vertices, our new splitting strategy produces a decomposition {T T 1 , . . . , T T p } into tiny colored triangulations satisfying the Hypotheses 1, 2, 3, 4 and 5, and hence yields a succinct representation of T requiring asymptotically 3.24n + o(n) bits.

Table 1 :

 1 Comparison of existing compact representations for simple planar graphs, with e edges, m faces and n vertices (lower order terms are omitted).

	Algorithm	triangulated	3-connec.
	Munro Raman (Focs 97)	2e + 8n or 7m	2e + 8n
	Chuang et al. (Icalp 98)	2e + n or 3.5m	2e + 2n
	Chiang et al. (Soda 01)	2e + 2n or 4m	2e + 2n
	Castelli Aleardi et al. (Wads 05)	2.175m	-
	our new encodings	1.62m	2e

As done in related works on compact encodings, we use the term entropy to indicate the information theoretic lower bound. Let us observe that we will consider classes of graphs with uniform distribution.

We suppose that external data can be stored on O(lg n) bits.

Acknowledgments This work has been supported by the French "ACI Masses de données" program, via the Geocomp project, http://www.lix.polytechnique.fr/~schaeffe/GeoComp/.

This work has been supported by the French "ACI Masses de données" program, via the Geocomp project