Given a graph G = (V, E), two players, Alice and Bob, alternate their turns to choose uncolored edges to be colored. Whenever an uncolored edge is chosen, it is colored by the least positive integer so that no monochromatic cycle is created. Alice¡¦s goal is to minimize the total number of colors used in the game, while Bob¡¦s goal is to maximize it. The game Grundy arboricity of G is the number of colors used in the game when both players use optimal strategies. This thesis discusses the game Grundy arboricity of graphs. It is proved that if a graph G has arboricity k, then the game Grundy arboricity of G is at most 3k − 1. If a graph G has an acyclic orientation D with maximum out-degree at most k, then the game Grundy arboricity of G is at most 3k − 2.

We explore the problem of transforming plane triangulations using simultaneous diagonal flips. Wagner showed that any n-vertex plane triangulation can be transformed to any other plane triangulation on equal number of vertices using a finite sequence of diagonal flips. Later on it has been established that O(n) individual flips suffice to complete this transformation. Bose et al. showed that the transformation can also be done in 4 × ( 2 / log 54/53 + 2 / log 6/5 ) logn + 2 ≈ 327.1 log n simultaneous flips. This bound is asymptotically tight. We present two algorithms to improve the leading coefficient of this bound for transforming any plane triangulation into any other. The first of the two algorithms lowers this bound down to 4 × ( 2 / log 12/11 + 2 / log 9/7 ) logn + 2 ≈ 85.8 log n. By processing and preprocessing the interior and exterior of the triangulation’s Hamiltonian cycle parallelly in an interlaced fashion, we make further improvement of the algorithm from ≈ 327.1 log n down to 12 / log 6/5 logn + 2 ≈ 45.6 log n.

Given a simple graph G with vertex set V(G)={1,2,...,n} define S(G) to be the set of all real symmetric matrices A such that for all i not equal to j, the ijth entry of A is nonzero if and only if ij is in E(G). The range of the ranks of matrices in S(G) is of interest and can be determined by finding the minimum rank. The minimum rank of a graph, denoted mr(G), is the minimum rank achieved by a matrix in S(G). The maximum nullity of a graph, denoted M(G), is the maximum nullity achieved by a matrix in S(G). Note that mr(G)+M(G)=|V(G)| and so in finding the maximum nullity of a graph, the minimum rank of a graph is also determined. The minimum rank problem for a graph G asks us to determine mr(G) which in general is very difficult. A simple graph is planar if there exists a drawing of G in the plane such that any two line segments representing edges of G intersect only at a point which represents a vertex of G. A planar drawing partitions the rest of the plane into open regions called faces. A graph is outerplanar if there exists a planar drawing of G such that every vertex lies on the outer face. We consider the class of outerplanar graphs and summarize some of the recent results concerning the minimum rank problem for this class. The path cover number of a graph, denoted P(G), is the minimum number of vertex-disjoint paths needed to cover all the vertices of G. We show that for all outerplanar graphs G, P(G)is greater than or equal to M(G). We identify a subclass of outerplanar graphs, called partial 2-paths, for which P(G)=M(G). We give a different characterization for another subset of outerplanar graphs, unicyclic graphs, which determines whether M(G)=P(G) or M(G)=P(G)-1. We give an example of a 2-connected outerplanar graph for which P(G) ≥ M(G).A cover of a graph G is a collection of subgraphs of G such that the union of the edge sets of the subgraphs is equal to the E(G). The rank-sum of a cover C of G is denoted as rs(C) and is equal to the sum of the minimum ranks of the subgraphs in C. We show that for an outerplanar graph G, there exists an edge-disjoint cover of G consisting of cliques, stars, cycles, and double cycles such that the rank-sum of the cover is equal to the minimum rank of G. Using the fact that such a cover exists allows us to show that the minimum rank of a weighted outerplanar graph is equal to the minimum rank of its underlying simple graph.

Savoir comment transmettre une information est fondamental dans un réseau. Il est essentiel que chaque entité du réseau soit capable de décider localement, avec sa vue du réseau, du chemin par lequel l'information doit passer. Ainsi, il est souvent utile d'étudier la topologie du réseau, modélisée par un graphe, pour répondre à ces exigences. Nous nous intéressons dans un premier temps, à la décomposition arborescente des graphes planaires. En effet, comme dans beaucoup de problèmes de graphes, l'étude de la topologie des graphes nous conduit à procéder à une décomposition du graphe afin d'exploiter les propriétés structurelles qui en découlent. En suite, nous nous sommes aussi intéressés à la structure des graphes qui excluent un mineur H, en particulier le graphe K_{2,r}. Ces travaux nous ont permis d'améliorer les bornes actuelles connues sur la largeur arborescente de ces graphes. Dans la dernière partie, nous abordons le problème du routage compact. Nous nous sommes intéressés aux schémas de routage de plus courts chemins utilisant des adresses, des tables de routage de tailles optimales de O(log n) bits, où n est le nombre de sommets du graphe. Nous proposons un tel schéma de routage pour une famille de graphes valués contenant les arbres et les graphes planaire-extérieurs. / In a network, it is crucial to know how to construct an efficent routing scheme. It is fundamental for each entity with its local knowledge of the network, to be able to decide on which link to forward messages. Thus, it is important to sutdy the underlying network topology in order to design routing schemes. In the first part of this thesis, we construct a new tree-decomposition for planar graphs. In fact, as in many graph problems, the study of the graph structure leads to do a tree-decomposition for exploiting structural propertys of the graphs. In second part, we studied the structure of H-minor free graphs, in particular whenever H = K_{2,r}. Our results improve upon previous known bounds about the tree-width of K_{2,r}-minor free graphs. At last, we treat the problème of compact routing scheme. More precisely, we are interested in shortest-path routing schemes that use O(\log n) bits for addresses, headers and routing tables, where n is the number of vertices in the graph. We propose such a routing scheme for a large family of weighted graphs including outerplanar graphs.