Search

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.

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.