Cette thèse s'articule autour de la notion de plongement de graphe. Un plongement de graphe consiste à envoyer les sommets d'un graphe dans une autre structure par une application qui conserve certaines propriétés à déterminer. Nous pouvons distinguer deux grandes familles de plongements. D'une part les plongements purement combinatoires qui envoient les éléments d'un graphe G dans un autre graphe H. La propriété la plus naturelle à conserver est la notion d'adjacence entre les sommets. Nous nous intéressons à la conservation d'une propriété supplémentaire : la distance entre les sommets. Nous caractérisons plusieurs familles de graphes se plongeant de cette façon dans les hypercubes ou les graphes de Hamming. Les plongements topologiques visent à représenter un graphe G sur une surface quelconque. Les sommets sont envoyés vers des points d'une surface et les arêtes vers des courbes continues entre ces points. Comment représenter un graphe afin de minimiser le nombre de croisements d'arêtes ? Nous nous posons ces questions à travers l'étude de la planarité et des nombres de croisements de certains graphes.

Nous considérons le problème de concevoir des représentations compactes ou succinctes de structures de données géométriques. Dans ce cadre, en plus des questions de simple compression, l'attention est portée sur l'étude de structures de données nécessitant une petite quantité de ressources mémoire et permettant de répondre à des requêtes locales en temps O(1). L'une des contributions de cette thèse consiste à proposer un cadre algorithmique général pour la conception de représentations compactes de structures telles que les graphes planaires et les maillages surfaciques. Comme application nous présentons différentes structures spécialement conçues pour représenter de manière compacte la connectivité (ou information combinatoire) de certaines classes de graphes localement planaires. Pour le cas des triangulations planaires à m faces, nous proposons une représentation compacte de l'information combinatoire nécessitant asymptotiquement 2:175 bits par triangle pour le coût en espace et qui permet la navigation entre triangles adjacents, ainsi que d'autres requêtes locales d'incidence entre sommets, en temps constant : cette structure est ainsi optimale pour la classe des triangulations ayant un bord de taille arbitraire. Une telle représentation reste valide et optimale dans le cas de triangulations d'une surface de genre g borné : O(g lgm) bits supplémentaires sont alors nécessaires. Cette représentation est bien adaptée pour faire une mise à jour locale efficace de la triangulation. Plus précisément, il est possible d'effectuer des mises à jour en temps O(1) amorti après insertion de sommets, et en temps O(log2m) amorti après suppression de sommets et flip d'arêtes. Et en ce qui concerne les triangulations et les graphes planaires 3-connexes, correspondant aux maillages triangulaires et polygonaux homéomorphes à une sphère, nous proposons les premières représentations succinctes optimales : elles atteignent l'entropie respective des deux classes, 2 bits par arête pour les graphes 3-connexes, et 1:62 bits par triangle (ou 3:24 bits par sommet) pour les triangulations. Ces structures permettent aussi l'accès en temps O(1) aux informations associées aux sommets, notamment leurs coordonnées. Cependant nous ne traitons pas ici la compression de cette information géométrique.

Les biopuces sont utilisées en biologie moléculaire et pour le diagnostic. La lecture est généralement réalisée en «end-point» mais le suivi en temps réel donne accès à des données complémentaires. Avec les biopuces à fluorescence, ces expériences sont limitées par 1fluorescence de la solution d'hybridation contenant les cibles marquées. Pour atténuer ce signal parasite, il est possible d'exciter sélectivement la surface avec une onde guidée dans le substrat. L'utilisation de guides d'ondes minces permet de diminuer le signal parasite d'un facteur 103 et d'augmenter l'éclairement d'un facteur 104 par effet de confinement. La principale difficulté concerne le couplage de l'onde guidée. Dans ce travail, nous proposons un système de couplage innovant, simple et efficace basé sur l'incorporation de fluorophores dans les guides. Tout d'abord, un procédé sol-gel de synthèse à basse température de guide d'ondes à haut indice avec de faibles pertes optiques a été développé. Un chélate d'europium est ensuite incorporé à la matrice pour le couplage. Les couches dopées ont de bonnes propriétés optiques et des taux d'absorption élevés. La fluorescence guidée des sources permet l'excitation de spots biologiques ce qui valide l'architecture proposée. L'éclairement est homogène avec une sensibilité équivalente à celle d'un système conventionnel. Enfin, la fonctionnalisation de la surface a été étudiée pour permettre l'accrochage de biomolécules en surface. Le système développé a permis la réalisation d'expériences biologiques complètes en présence d'une solution d'hybridation. Une diminution significative de la fluorescence parasite a été mesurée par rapport au système conventionnel.

Dans cette thèse, nous nous intéressons à la coloration circulaire des graphes planaires. Des bornes supérieures ont été données pour des graphes avec degré maximum borné, avec girth, la longueur de son plus petit cycle, bornée, avec des cycles manquants, etc. Ici nous donnerons de nouvelles bornes pour les graphes avec degré moyen maximum borné. Nous étudions également la coloration totale et la coloration (d,1)-totale de plusieurs familles infinies de graphes. Nous décrivons le nouveau concept de coloration (d,1)-totale circulaire. Enfin, nous discutons les conditions nécessaires pour qu'un graphe planaire admette une coloration acyclique par listes de taille 4. / In this thesis, we study the circular coloring of planar graphs. Upper bounds have been given for graphs with bounded maximum degree, with bounded girth, that is the length of its smallest cycle, with missing cycles, and so on. It has also been studied for graphs with bounded maximum average degree. Here we give new upper bounds for that latter case. We also study the total coloring and ($d,1$)-total labeling of a few infinite families of graphs and describe the new concept of circular ($d,1$)-total labeling of graphs. In the last part, we will discuss conditions for a planar graph to be acyclically $4$-choosable.

.

Les réaliseurs, ou arbres de Schnyder, ont été introduits par Walter Schnyder à la fin des années 80 pour caractériser les graphes planaires, puis pour dessiner ces mêmes graphes sur des grilles $(n-2)\times(n-2)$.<br>Dans ce document nous proposons dans un premier temps une extension du théorème de Wagner aux réaliseurs, qui nous permet d'établir une relation entre le nombre de feuilles et le nombre de faces tricolores d'un réaliseur.<br>Ensuite, à l'aide d'une bijection entre les réaliseurs et les paires de chemins de Dyck qui ne se coupent pas, nous énumérons les réaliseurs. Un algorithme de génération aléatoire de $p$ chemins de Dyck ne se coupant pas, est également présenté. Il permet en outre de générer aléatoirement des réaliseurs en temps linéaire.<br>Puis nous montrons que grâce aux réaliseurs, il est possible de dessiner, à l'aide de lignes brisées des graphes planaires sur des grilles de largeur et de surface optimales.<br>Enfin, nous proposons une généralisation des réaliseurs minimaux aux graphes planaires connexes : les arbres recouvrants bien-ordonnés. Grâce à cette généralisation ainsi qu'à une méthode de triangulation adaptée nous proposons un algorithme de codage des graphes planaires à $n$ sommets en $5,007n$ bits.

L'étude des cycles, flots et chemins des graphes est intimement liée au développement de l'optimisation combinatoire. Dans l'introduction nous mettons en parallèle ces concepts à partir de résultats classiques, et les deux autres parties de la thèse développent les nouveaux résultats dans deux directions différentes. La première porte sur les problèmes d'existence de multiflots entiers. Plusieurs paramètres naturels s'appliquent à ces problèmes, générant plus d'une centaine de cas. Après un rappel des résultats de la littérature sous une forme synthétique, nous résolvons plusieurs problèmes ouverts. En particulier, nous montrons que trouver deux flots disjoints dans les graphes planaires est un problème NP-complet. Nous donnons aussi un algorithme polynomial pour router les digraphes planaires acycliques eulériens, lorsque le nombre de classes d'arcs de demande est fixé. Ensuite, nous nous intéressons au problème consistant à trouver une plus courte marche fermée passant par tous les sommets d'un graphe. Spéciquement, nous cherchons à caractériser les graphes pour lesquels une bonne caractérisation est donnée par des empilements d'ensembles éclatants. Nous présentons quelques résultats de nature polyédrale, puis étudions le cas des cographes et des graphes d'intervalles.

Dans cette thèse, nous nous intéressons à différentes notions de colorations sous contraintes. Nous nous intéressons plus spécialement à la coloration acyclique, à la coloration forte d'arêtes et à la coloration d'arêtes sommets adjacents distinguants.Dans le Chapitre 2, nous avons étudié la coloration acyclique. Tout d'abord nous avons cherché à borner le nombre chromatique acyclique pour la classe des graphes de degré maximum borné. Ensuite nous nous sommes attardés sur la coloration acyclique par listes. La notion de coloration acyclique par liste des graphes planaires a été introduite par Borodin, Fon-Der Flaass, Kostochka, Raspaud et Sopena. Ils ont conjecturé que tout graphe planaire est acycliquement 5-liste coloriable. De notre côté, nous avons proposé des conditions suffisantes de 3-liste coloration acyclique des graphes planaires. Dans le Chapitre 3, nous avons étudié la coloration forte d'arêtes des graphes subcubiques en majorant l'indice chromatique fort en fonction du degré moyen maximum. Nous nous sommes également intéressés à la coloration forte d'arêtes des graphes subcubiques sans cycles de longueurs données et nous avons également obtenu une majoration optimale de l'indice chromatique fort pour la famille des graphes planaires extérieurs. Nous avons aussi présenté différents résultats de complexité pour la classe des graphes planaires subcubiques. Enfin, au Chapitre 4, nous avons abordé la coloration d'arêtes sommets adjacents distinguants en déterminant les majorations de l'indice avd-chromatique en fonction du degré moyen maximum. Notre travail s'inscrit dans la continuité de celui effectué par Wang et Wang en 2010. Plus précisément, nous nous sommes focalisés sur la famille des graphes de degré maximum au moins 5.

Dans cette thèse, nous nous intéressons à trois problèmes issus de l'informatique théorique, à savoir le placement de formes rectangulaires dans un conteneur (OPP), la coloration dite "forte" d'arêtes des graphes et les codes identifiants dans les graphes. L'OPP consiste à décider si un ensemble d'items rectangulaires peut être placé sans chevauchement dans un conteneur rectangulaire et sans dépassement des bords de celui-ci. Une contrainte supplémentaire est prise en compte, à savoir l'interdiction de rotation des items. Le problème est NP-difficile même dans le cas où le conteneur et les formes sont des carrés. Nous présentons un algorithme de résolution efficace basé sur une caractérisation du problème par des graphes d'intervalles, proposée par Fekete et Schepers. L'algorithme est exact et utilise les MPQ-arbres - structures de données qui encodent ces graphes de manière compacte tout en capturant leurs propriétés remarquables. Nous montrons les résultats expérimentaux de notre approche en les comparant aux performances d'autres algorithmes existants. L'étude de la coloration forte d'arêtes et des codes identifiants porte sur les aspects structurels et de calculabilité de ces deux problèmes. Dans le cas de la coloration forte d'arêtes nous nous intéressons plus particulièrement aux familles des graphes planaires et des graphes subcubiques. Nous montrons des bornes optimales pour l'indice chromatique fort des graphes subcubiques en fonction du degré moyen maximum et montrons que tout graphe planaire subcubique sans cycles induits de longueur 4 et 5 est coloriable avec neuf couleurs. Enfin nous confirmons la difficulté du problème de décision associé, en prouvant qu'il est NP-complet dans des sous-classes restreintes des graphes planaires subcubiques. La troisième partie de la thèse est consacrée aux codes identifiants. Nous proposons une caractérisation des graphes identifiables dont la cardinalité du code identifiant minimum est n − 1, où n est l'ordre du graphe. Nous étudions la classe des graphes adjoints et nous prouvons des bornes inférieures et supérieures serrées pour la cardinalité du code identifiant minimum dans cette classe. Finalement, nous montrons qu'il existe un algorithme linéaire de calcul de ce paramètre dans la classe des graphes adjoints L(G) où G a une largeur arborescente bornée par une constante. En revanche nous nous apercevons que le problème est NP-complet dans des sous-classes très restreintes des graphes parfaits.

Dans cette thèse, nous nous intéressons à deux types de décompositions des graphes introduits par Robertson et Seymour: les décompositions arborescentes et les décompositions en branches. À ces décompositions sont associés deux paramètres des graphes: la largeur arborescente et la largeur de branches. Nous montrons que ces deux décompositions peuvent être vues comme issues d'une même structure combinatoire; les deux paramètres mentionné ci-dessus sont égaux aux valeurs minimales de deux paramètres de cette structure commune. En poussant plus avant cette analogie, nous montrons comment adapter une technique de calcul de la largeur arborescente au calcul de la largeur de branches. Ceci nous permet de calculer la largeur de branches des graphes de nombre astéroïde borné ayant un nombre polynômial de séparateurs minimaux et celle des graphes d-trapézoïdes circulaires. Ce parallèle nous permet aussi d'adapter certains résultats structurels sur les décompositions en branches aux décompositions arborescentes. Dans le cas des graphes planaires, nous interprétons ces propriétés à l'aide d'outils topologiques. De cette façon, nous donnons une démonstration simple d'un théorème de dualité reliant la largeur arborescente d'un graphe planaire et celle de son dual. Ces outils nous permettent aussi d'énumérer de façon efficace les séparateurs minimaux des graphes planaires.