L'évolution de l'infographie et des techniques de numérisation a récemment ouvert la voie à une modélisation tridimensionnelle du monde qui nous entoure. Afin de s'adapter à l'hétérogénéité des ressources et médias manipulant ces objets 3D, des techniques basées sur l'analyse multirésolution sont généralement utilisées car elles fournissent une représentation "scalable" de ces modèles géométriques. C'est dans ce cadre de compression et de transmission progressive d'objets 3D (modélisées sous forme de maillages surfaciques) que se situe ce travail de thèse, réalisé dans le cadre du projet "CoSurf" (collaboration entre le laboratoire LIRIS et France Télécom R&D Rennes). Nous proposons ainsi une nouvelle méthode de compression hiérarchique s'appuyant sur une décomposition en ondelettes, outil d'analyse performant et robuste qui a fait ses preuves en termes de compression d'images et de vidéos. Notre méthode se démarque des techniques existantes, puisqu'elle s'appuie sur une segmentation préalable de la surface en régions d'amplitudes fréquentielles variables. Les partitions résultantes peuvent ainsi être traitées indépendamment durant les phases d'analyse multirésolution, de quantification et d'allocation binaire, de façon à s'adapter aux caractéristiques surfaciques locales des maillages et ainsi réduire les informations à coder. La contribution visuelle de chacune des partitions à l'ensemble de la surface est également un point important à considérer dans la phase d'optimisation des bits alloués à celles-ci, notamment pour des applications comme la transmission et la visualisation sélectives. D'autres applications telles que le tatouage, le filtrage ou le débruitage adaptatifs, l'indexation ou enfin la correction d'erreurs après transmission sur un canal bruité, pourraient bénéficier de ce concept générique que nous avons proposé.

Dans le cadre de la géométrie riemannienne globale sans hypothèse de courbure en lien avec la topologie, nous nous intéressons au volume maximal des boules de rayon fixé dans les revêtements universels des graphes et des surfaces. Dans la première partie, nous prouvons que si l’aire d’une surface riemannienne fermée M de genre g ≥ 2 est suffisamment petite par rapport à son aire hyperbolique, alors pour chaque rayon R ≥ 0, le revêtement universel de M contient une R-boule d’aire au moins l’aire d’une cR-boule dans le plan hyperbolique, où c ∈ (0; 1) est une constante universelle. En particulier (quitte à prendre l’aire de la surface encore plus petite), nous démontrons que pour chaque rayon R ≥ 1, le revêtement universel de M contient une R-boule d’aire au moins l’aire d’une R-boule dans le plan hyperbolique. Ce résultat répond positivement pour les surfaces, à une question de L. Guth. Nous démontrons également que si Γ est un graphe connexe de premier nombre de Betti b ≥ 2 et de longueur suffisamment petite par rapport à la longueur d’un graphe trivalent Γb de premier nombre de Betti b dont la longueur de chaque arête est 1, alors pour chaque rayon R ≥ 0, le revêtement universel de Γ contient une R-boule d’aire au moins c fois l’aire d’une R-boule dans le revêtement universel de Γb, où c ∈ ( ½ ; 1). / This thesis deals with global Riemannian geometry without curvature assumptions and its link to topology, we focus on the maximal volume of balls of fixed radius in the universal covers of graphs and surfaces. In the first part, we prove that if the area of a closed Riemannian surface M of genus at least two is sufficiently small with respect to its hyperbolic area, then for every radius R ≥ 0 the universal cover of M contains an R-ball with area at least the area of a cR-ball in the hyperbolic plane, where c ∈ (0; 1) is a universal positive constant. In particular (taking the area of M smaller if needed), we prove that for every radius R ≥ 1, the universal cover of M contains an R-ball with area at least the area of a ball with the same radius in the hyperbolic plane. This result answers positively a question of L. Guth for surfaces. We also prove an analog result for graphs. Specifically, we prove that if Γ is a connected metric graph of first Betti number b ≥ 2 and of length sufficiently small with respect to the length of a connected trivalent graph Γb of the same Betti number where the length of each edge is 1, then for every radius R ≥ 0 the universal cover of Γ contains an R-ball with length at least c times the length of an R-ball in the universal cover of Γb, where c ∈ ( ½ ; 1) is a universal constant.

Cette thèse étudie les aspects combinatoires, algorithmiques et la complexité de problèmes de théorie des graphes, et tout spécialement de problèmes liés aux notions de marches, de transitions et de distance dans les graphes. Nous nous intéressons d’abord au problème de traffic monitoring, qui consiste à placer aussi peu de capteurs que possible sur les arcs d’un graphe de façon à pouvoir reconstituer des marches d’objets. La caractérisation d’instances intéressantes dans la pratique nous amène à la notion de transitions interdites, qui renforce le modèle de graphe. Notre travail sur les graphes à transitions interdites comprend aussi l’étude de la notion d’ensemble de transitions connectant, que l’on peut voir comme l’analogue en terme de transitions de la notion d’arbre couvrant. Une partie importante de cette thèse porte sur les graphes géométriques, qui sont des graphes dont les sommets sont des points de l’espace réel et dont les arêtes sont déterminées par les distances géométriques entre les sommets. Ces graphes sont au coeur du célèbre problème de Hadwiger-Nelson et nous sont d’une grande aide dans notre étude de la densité des ensembles qui évitent la distance 1 dans plusieurs types d’espaces normés. Nous développons des outils pour étudier ces problèmes et les utilisons pour prouver la conjecture de Bachoc-Robins sur plusieurs paralléloèdres. Nous nous penchons aussi sur le cas du plan euclidien et améliorons les bornes sur la densité des ensembles évitant la distance 1 et sur son nombre chromatique fractionnaire. Enfin, nous étudions la complexité de problèmes d’homomorphismes de graphes et établissons des théorèmes de dichotomie sur la complexité des homomorphismes localement injectifs vers les tournois réflexifs. / This thesis studies combinatorial, algorithmic and complexity aspects of graph theory problems, and especially of problems related to the notions of walks, transitions and distances in graphs. We first study the problem of traffic monitoring, in which we have to place as few censors as possible on the arcs of a graph to be able to retrace walks of objects. The characterization of instances of practical interests brings us to the notion of forbidden transitions, which strengthens the model of graphs. Our work on forbidden-transition graphs also includes the study of connecting transition sets, which can be seen as a translation to forbidden-transition graphs of the notion of spanning trees. A large part of this thesis focuses on geometric graphs, which are graphs whose vertices are points of the real space and whose edges are determined by geometric distance between the vertices. This graphs are at the core of the famous Hadwiger- Nelson problem and are of great help in our study of the density of sets avoiding distance 1 in various normed spaces. We develop new tools to study these problems and use them to prove the Bachoc-Robins conjecture on several parallelohedra. We also investigate the case of the Euclidean plane and improve the bounds on the density of sets avoiding distance 1 and on its fractional chromatic number. Finally, we study the complexity of graph homomorphism problems and establish dichotomy theorems for the complexity of locally-injective homomorphisms to reflexive tournaments.