Search

This thesis falls within the theoretical computer science field of graph theory, and deals with a question asked in 1968 by Tibor Gallai, still unanswered as of today. Gallai conjectured that the edges of any connected graph with n vertices can be partitioned into [(n+1)/2] paths. Although this conjecture has been tackled and partially solved over the years, the property has only been proven on very specific graph classes, which include graphs in which the vertices of even degree form a forest (Pyber, 1996), graphs of maximum degree 5 (Bonamy, Perrett, 2016) or graphs of treewidth at most 3 (Botler et al., 2018). The planar graphs are the graphs that can be embedded in the plane, or drawn without edges crossing. The class of planar graphs is well-known in graph theory and has been thoroughly studied. Botler, Jiménez and Sambinelli recently confirmed the conjecture on triangle-free planar graphs.Our result consists in a proof of the conjecture on the whole class of planar graphs. This class is significantly broader and more general than those of previous results, and in our opinion constitutes an important contribution to the study of Gallai's conjecture. More precisely, we work on a stronger variant of the conjecture, proposed by Bonamy and Perrett in 2016, which states that all connected graphs on n vertices could be decomposed into [n/2] paths, with the exception of a family of dense graphs. We confirm this conjecture in the case of planar graphs, by showing that every connected planar graph except K3 and K5- (K5 minus one edge) can be decomposed into [n/2] paths. The proof is divided into three parts: the first two show the main lemma of the proof, which restricts the structure of a hypothetical vertex-minimum counterexample to the statement, while the third part uses the main lemma to show that such a counterexample does not exist., Cette thèse s'inscrit dans le domaine informatique de la théorie des graphes, et traite d'une question posée en 1968 par Tibor Gallai, toujours sans réponse aujourd'hui. Gallai conjectura que les arêtes de tout graphe connexe à n sommets pouvaient être partitionnées en [(n+1)/2] chemins. Bien que cette conjecture fut attaquée et partiellement résolue au fil des ans, la propriété n'a été prouvée que pour des classes de graphes très spécifiques, comme les graphes dont les sommets de degré pair forment une forêt (Pyber, 1996), les graphes de degré maximum 5 (Bonamy, Perrett, 2016) ou les graphes de largeur arborescente au plus 3 (Botler et al., 2018). Les graphes planaires sont les graphes qui peuvent être plongés dans le plan, c'est-à-dire dessinés sans croisements d'arêtes. C'est une classe bien connue dans la théorie des graphes, et largement étudiée. Botler, Jiménez et Sambinelli ont récemment confirmé la conjecture dans le cas des graphes planaires sans triangles.Notre résultat consiste en une preuve de la conjecture sur la classe générale des graphes planaires. Cette classe est notablement plus générale que celles des précédents résultats, et de notre point de vue constitue une importante contribution à l'étude de la conjecture de Gallai. Plus précisément, nous travaillons sur une version plus forte de la conjecture, proposée par Bonamy et Perrett en 2016, et qui énonce que les graphes connexes à n sommets peuvent être décomposés en [n/2] chemins, à l'exception d'une famille de graphes denses. Nous confirmons cette conjecture dans le cas des graphes planaires, en démontrant que tout graphe planaire, à l'exception de K3 et de K5- (K5 moins une arête), peut être décomposé en [n/2] chemins. La preuve est divisée en trois parties : les deux premières montrent le lemme principal de la preuve, qui restreint la structure d'un contre-exemple hypothétique ayant un minimum de sommets, et la troisième partie utilise ce lemme pour montrer qu'un tel contre-exemple n'existe pas.

In this thesis, we present results obtained in two fields: formal language theory and graph theory. In formal language theory, we consider some problems of characterization of classes of regular languages. The generic problem consists in determining whether a given regular language can be defined in a fixed formalism. The current approaches use a more general problem called separation. We present here two types of contributions: a generalization of a decidability result to the setting of infinite words, together with lower bounds for the complexity of the separation problem. In graph theory, we consider the classical problem of graph coloring, where we assign colors to vertices of a graph in such a way that two adjacent vertices receive different colors. The goal is to use the fewest colors. When the graphs are sparse, a crucial tool for this is the discharging method. It is most notably decisive in the proof of the Four-Color Theorem. This method can be seen as an unconventional construction of an inductive proof scheme, specific to the considered problem and graph class, where arguing the validity of the scheme is rarely immediate. We use variants of the discharging method to study two types of coloring problems., Cette thèse présente des résultats obtenus dans deux domaines : la théorie des langages, et la théorie des graphes. En théorie des langages, on s’intéresse à des problèmes de caractérisation de classes de langages réguliers. Le problème générique consiste à déterminer si un langage régulier donné peut être défini dans un certain formalisme. Les méthodes actuelles font intervenir un problème plus général appelé séparation. On présente ici deux types de contributions : une généralisation d’un résultat de décidabilité au cadre des langages de mots infinis, ainsi que des bornes inférieures pour la complexité du problème de séparation. En théorie des graphes, on considère le problème classique de coloration de graphes, où on cherche à attribuer des couleurs aux sommets d’un graphe de sorte que les sommets adjacents reçoivent des couleurs différentes, le but étant d’utiliser le moins de couleurs possible. Dans le cas des graphes peu denses, la méthode de déchargement est un atout majeur. Elle a notamment joué un rôle décisif dans la preuve du théorème des quatre couleurs. Cette méthode peut être vue comme une construction non conventionnelle d’un schéma de preuve par induction, spécifique à la classe de graphes et à la propriété considérées, et où la validité du schéma est rarement immédiate. On utilise des variantes de la méthode de déchargement pour étudier deux types de problèmes de coloration.

Wireless Sensor Networks (WSNs) are a special class of Ad hoc networks, which are under intensive research.They are considered as a very powerful tool to connect the physical and the digital worlds. They consist of a largenumber of sensor nodes that are characterized with limited resources in terms of energy, range of sensing and communication, processing speed and storage capacity.They are deployed in an indoor or outdoor environment in many application domains such as army, environment, health, home and agriculture. The scarcity of sensor node resources and the unreliability of wireless links drive most of the research issues in the field of WSNs, namely energy, coverage, connectivity, routing, fault tolerance and security. The aim of this thesis is to propose an energyefficient and reliable cross-layer surveillance protocol for sensitive fenced areas, such as oil or nuclear sites, using duty-cycled WSNs with asymmetrical links due to the radio irregularity phenomenon. Initially, the proposed protocol identifies the boundary nodes of the deployedWSN, to be used as sentinel nodes, i.e., nodes that are always in an active state. The remaining nodes are usedas duty-cycled relay nodes during the routing phase to relay alerts towards the sink. The boundary nodes identification process and alert routing are both performed using an enhanced version of the Greedy Perimeter Stateless Routing (GPSR) protocol, referred to as GPSR over Symmetrical Links (GPSR-SL) and which relies on a Non Unit Disk Graph (N-UDG). The proposed cross-layer surveillance protocol has been implemented and its performance has been evaluated under the OMNeT++/Castalia simulation environment. Performance results show that this protocol achieves higher Packet Delivery Ratio by up to 3.63%, energy .efficiency and satisfactory latency when compared to the same protocol based on the original GPSR., Les Réseaux de Capteurs Sans Fil (RCSFs) constituent une classe particulière des réseaux Ad hoc, faisant l'objet de recherches intensives. Ils sont considérés comme un outil très puissant pour connecter le monde physique et le monde numérique. Ils se composent d'un grand nombre de noeuds capteurs dotés de ressources limitées en termes d'énergie, de portée de capture et de communication, de vitesse de traitement et de capacité de stockage. Ils sont déployés dans un environnement intérieur ou extérieur, et ce dans de nombreux domaines d'application tels que l'armée, l'environnement, la santé, la maison et l'agriculture. La rareté des ressources des noeuds capteurs et la non fiabilité des liaisons sans fil motivent la plupart des problématiques dans le domaine des RCSFs, à savoir l'énergie, la couverture, la connectivité, le routage, la tolérance aux pannes et la sécurité. L'objectif de cette thèse est de proposer un protocole de surveillance inter-couches, à efficacité énergétique et fiable, pour la surveillance des zones sensibles clôturées, tel qu'un site pétrolier ou nucléaire, utilisant les réseaux de capteurs sans fil avec un cycle d'activité, et avec prise en compte des liens asymétriques dus au phénomène de l'irrégularité de la radio. Initialement, le protocole proposé identifie les noeuds de bordure du RCSF pour les utiliser comme nœuds sentinelles, c.-à-d., des noeuds qui sont toujours dans un état actif. Les noeuds restants sont utilisés en tant que noeuds relais avec un cycle d'activité, pendant la phase de routage des alertes vers le noeud puits. Le processus d'identification des noeuds de bordure ainsi que le routage des alertes, sont assurés par le protocole Greedy Perimeter Stateless Routing through Symmetrical Links (GPSR-SL) qui est une version améliorée du protocole GPSR, reposant sur un graphe de connectivité représenté sous forme de disques non-unité (N-UDG). Le protocole de surveillance inter-couches proposé a été implémenté et ses performances ont été évaluées en utilisant l'environnement de simulation OMNeT++/Castalia. Les résultats de performance montrent que ce protocole permet d'obtenir un ratio de livraison de paquets plus élevé d'environ 3.63%, une efficacité énergétique et une latence satisfaisante par rapport au même protocole basé sur le GPSR original.

National audience

In this thesis, we present results on three different problems concerning planar graphs. We first give some new results on planar non-aligned drawings, i.e., planar grid drawings where vertices are all on different rows and columns. We show that not every planar graph has a non-aligned drawing on a grid with n rows and columns, but we present two algorithms generating a non-aligned polyline drawings on such a grid requiring either n − 3 or min( (2n−5)/3 , #{separating triangles} + 1) bends in total. Concerning non-minimal grids, we give two algorithms drawing a planar non-aligned drawing on grids with area O(n^4). We also give specific results for 4-connected graphs and nested-triangle graphs.The second topic is power domination in planar graphs. We present a family of graphs with power dominating number γ_P at least n/6 . We then prove that for every maximal planar graph G of order n, γ_P (G) ≤ (n−2)/4 , and we give a constructive algorithm. We also prove that for triangular grids Tk of dimension k with hexagonal-shape border, γ_P (Tk) = \lceil k/3 \rceil.Finally, we focus on the enumeration of planar Eulerian orientations. After proposing a new decomposition for these maps, we define subsets and supersets of planar Eulerian orientations with parameter k, generated by looking at the orientations of the last 2k − 1 edges around the root vertex. For each set, we give a system of functional equations defining its generating function, and we prove that it is always algebraic. This way, we show that the growth rate of planar Eulerian orientations is between 11.56 and 13.005., Dans cette thèse, nous étudions trois problèmes concernant les graphes planaires.Nous travaillons tout d’abord sur les dessins planaires non-alignés, c’est-à-dire des dessins planaires de graphes sur une grille sans que deux sommets se trouvent sur la même ligne ou la même colonne. Nous caractérisons les graphes planaires possédant un tel dessin sur une grille à n lignes et n colonnes, et nous présentons deux algorithmes générant un dessin planaire non-aligné avec arêtes brisées sur cette grille pour tout graphe planaire, avec n − 3 ou min( (2n−5)/3 , #{triangles séparateurs} + 1) brisures au total. Nous proposons également deux algorithmes dessinant un dessin planaire non-aligné sur des grilles d’aire O(n^4). Nous donnons des résultats spécifiques concernant les graphes 4-connexes et de typetriangle-emboîté.Le second sujet de cette thèse est la domination de puissance dans les graphes planaires. Nous exhibons une famille de graphes ayant un nombre de domination de puissance γ_P au moins égal à n/6 . Nous montrons aussi que pour tout graphe planaire maximal G à n ≥ 6 sommets, γ_P (G) ≤ (n−2)/4 . Enfin, nous étudions les grilles triangulaires Tk à bord hexagonal de dimension k et nous montrons que γ_P (Tk ) = \lceil k/3 \rceil.Nous étudions également l’énumération des orientations planaires Eulériennes. Nous proposons tout d’abord une nouvelle décomposition de ces cartes. Puis, en considérant les orientations des dernières 2k − 1 arêtes autour de la racine, nous définissons des sous- et sur-ensembles des orientations planaires Eulériennes paramétrés par k. Pour chaque classe, nous proposons un système d’équations fonctionnelles définissant leur série génératrice, et nous prouvons que celle-ci est toujours algébrique. Nous montrons ainsi que la constante de croissance des orientations planaires Eulériennes est comprise entre 11.56 et 13.005.

A proper vertex coloring of a graph $G$ is equitable if the sizes of color classes differ by at most one. The equitable chromatic threshold $\chi_{eq}^*(G)$ of $G$ is the smallest integer $m$ such that $G$ is equitably $n$-colorable for all $n\ge m$. We show that for planar graphs $G$ with minimum degree at least two, $\chi_{eq}^*(G)\le 4$ if the girth of $G$ is at least $10$, and $\chi_{eq}^*(G)\le 3$ if the girth of $G$ is at least $14$., Comment: In the journal version, Lemma 3.1 is incorrect as stated, so in the current version we replaced its unique use (in the proof of Lemma 3.2) by a direct argument and removed Lemma 3.1. The numbering follows that of the journal version, so there is no Lemma 3.1 in this article

This thesis focuses on two topics of graph algorithms. The first topic is network inference. How efficiently can we find an unknown graph using shortest path queries between its vertices? We assume that the graph has bounded degree. In the reconstruction problem, the goal is to find the graph; and in the verification problem, the goal is to check whether a given graph is correct. We provide randomized algorithms based on a Voronoi cell decomposition. Next, we analyze greedy algorithms, and show that they are near-optimal. We also study the problems on special graph classes, prove lower bounds, and study the approximate reconstruction. The second topic is optimization in planar graphs. We study two problems. In the correlation clustering problem, the input is a weighted graph, where every edge has a label of h+i or h−i, indicating whether its endpoints are in the same category or in different categories. The goal is to find a partition of the vertices into categories that tries to respect the labels. In the two-edge-connected augmentation problem, the input is a weighted graph and a subset R of edges. The goal is to produce a minimum-weight subset S of edges, such that for every edge in R, its endpoints are two-edge-connected in the union of R and S. For planar graphs, we reduce correlation clustering to two-edge-connected augmentation, and show that both problems, although they are NP-hard, have a polynomial-time approximation scheme. We build on the brick decomposition technique developed recently., Cette thèse porte sur deux sujets d’algorithmique des graphes. Le premier sujet est l’inférence de réseaux. Quelle est la complexité pour déterminer un graphe inconnu à partir de requêtes de plus court chemin entre ses sommets ? Nous supposons que le graphe est de degré borné. Dans le problème de reconstruction, le but est de reconstruire le graphe ; tandis que dans le problème de vérification, le but est de vérifier qu’un graphe donné est correct. Nous développons des algorithmes probabilistes utilisant une décomposition en cellules de Voronoi. Ensuite, nous analysons des algorithmes de type glouton, et montrons qu’ils sont quasi-optimaux. Nous étudions aussi ces problèmes sur des familles particulières de graphes, démontrons des bornes inférieures, et étudions la reconstruction approximative. Le deuxième sujet est l’étude de deux problèmes d’optimisation sur les graphes planaires. Dans le problème de classification par corrélations, l’entrée est un graphe pondéré, où chaque arête a une étiquette h+i ou h-i, indiquant si ses extrémités sont ou non dans la même catégorie. Le but est de trouver une partition des sommets en catégories qui respecte au mieux les étiquettes. Dans le problème d’augmentation 2-arête-connexe, l’entrée est un graphe pondéré et un sous-ensemble R des arêtes. Le but est de trouver un sous-ensemble S des arêtes de poids minimum, tel que pour chaque arête de R, ses extrémités sont dans une composante 2-arête-connexe de l’union de R et S. Pour les graphes planaires, nous réduisons le premier problème au deuxième et montrons que les deux problèmes, bien que NP-durs, ont un schéma d’approximation en temps polynomial. Nous utilisons la technique récente de décomposition en briques.

A partir du concept de paire d'amis dans un graphe (paire de sommets telle que toutes les chaînes sans cordes qui les relient sont de longueur paire) deux classes de graphes parfaits ont été déjà définies. La première notée QPS (graphes de quasi-parité stricte) est définie par l'existence de paires d'amis pour tout sous-graphe induit incomplet. La deuxième notée PC (graphes parfaitement contractibles) est définie à partir de l'idée algorithmique de coloration du graphe ou de ses sous-graphes induits par enchaînement de contractions successives des sommets d'une paire d'amis jusqu'à obtenir une clique, auquel cas la coloration est optimale. Dans cette thèse nous avons abordé deux conjectures: la première (relative à la classe QPS) énoncée par S. Hougardy est proche de la conjecture forte de graphes parfaits et la deuxième énoncée par H. Everett et B. Reed consite à caractériser les graphes PC par sous-graphes exclus. Nous avons pu valider ces deux conjectures dans deux cas: le cas des graphes planaires et le cas des graphes sans griffe. Ces quatre résultats sont assortis d'algorithmes polynomiaux de reconnaissance (ainsi que de coloration pour la classe PC)

L'organisation structurée (graphe avec hiérarchies et propriétés sémantiques) d'objets du plan implique plusieurs opérations complexes qui doivent être effectuées en toute sécurité de cohérence topologique. La précision inhérente d'une machine étant nécessairement limitée, il faut souvent recourir à une arithmétique exacte couteuse. Cette thèse présente, à partir de travaux liés à la réalisation du module de facettisation d'un simulateur de vol industriel, une solution permettant l'utilisation d'une arithmétique mixte, de précision arbitraire et de coût très inférieur statistiquement a la solution exacte. On y trouve aussi l'unification des méthodes de construction d'un diagramme de Voronoi, d'une triangulation de Delaunay pour un nuage de points dans le plan et de la triangulation contrainte de Delaunay de la représentation par segments d'un graphe planaire, autour d'une technique incrémentale optimale, fondamentalement plus simple que la méthode diviser-pour-résoudre classique. La technique incrémentale permet, par ailleurs, de donner un algorithme linéaire et très simple de construction du diagramme de Voronoi et de la triangulation de Delaunay d'un nuage de points situes sur la frontière d'un polygone monotone ou convexe., No abstract

Universités : Université scientifique et médicale de Grenoble et Institut National Polytechnique