Dans la théorie des graphes, un graphe planaire est un graphe qui a la particularité de pouvoir se représenter sur un plan sans qu'aucune arête (ou arc pour un graphe orienté) n'en croise une autre. Autrement dit, ces graphes sont précisément ceux que l'on peut plonger dans le plan, ou encore les graphes dont le nombre de croisements est nul. Les méthodes associées à ces graphes permettent de résoudre des problèmes comme l'énigme des trois maisons et d'autres plus difficiles comme le théorème des quatre couleurs. Exemples et contre-exemples 1) 2) 3) 4)

Ce graphe est clairement planaire, car il n'existe pas d'intersection entre deux arêtes.

C'est un graphe complet à quatre sommets (K4). Il est planaire : si on déplace le sommet 4 dans le triangle 1 2 3, on constate qu'il n'y a plus d'intersection d'arêtes.

C'est un graphe complet à 5 sommets (K5). Il n'est pas planaire.

C'est un graphe biparti complet K3,3 à 6 sommets, 3 d'entre eux se connectant aux trois autres.

Modeling and Controlling epidemics : a graph perspective

Philippe Sakari Rossinelli

The social and economical impact a virus has in a population is not negligible. For this reason, gaining a theoretical understanding of the behavior of a virus is of prime importance. This project is going to be divided in several parts. First, we will discuss the topology of different graphs. Secondly, we are going to talk about the propagation of a virus on a graph, and the optimal nodes to do that. We will introduce the notion of cost function, and how relevant it is. Lastly, we will be talking about vaccinating a graph.

2015

On the robustness of the metric dimension of grid graphs to adding a single edge

Satvik Mehul Mashkaria, Gergely Odor, Patrick Thiran

The metric dimension (MD) of a graph is a combinatorial notion capturing the minimum number of landmark nodes needed to distinguish every pair of nodes in the graph based on graph distance. We study how much the MD can increase if we add a single edge to the graph. The extra edge can either be selected adversarially, in which case we are interested in the largest possible value that the MD can take, or uniformly at random, in which case we are interested in the distribution of the MD. The adversarial setting has already been studied by [Eroh et. al., 2015] for general graphs, who found an example where the MD doubles on adding a single edge. By constructing a different example, we show that this increase can be as large as exponential. However, we believe that such a large increase can occur only in specially constructed graphs, and that in most interesting graph families, the MD at most doubles on adding a single edge. We prove this for

d

-dimensional grid graphs, by showing that

2d

appropriately chosen corners and the endpoints of the extra edge can distinguish every pair of nodes, no matter where the edge is added. For the special case of

d=2

, we show that it suffices to choose the four corners as landmarks. Finally, when the extra edge is sampled uniformly at random, we conjecture that the MD of 2-dimensional grids converges in probability to

3+\mathrm{Ber}(8/27)

, and we give an almost complete proof.

2022

On the robustness of the metric dimension of grid graphs to adding a single edge

Satvik Mehul Mashkaria, Gergely Odor, Patrick Thiran

d

-dimensional grid graphs, by showing that

2d

appropriately chosen corners and the endpoints of the extra edge can distinguish every pair of nodes, no matter where the edge is added. For the special case of

d=2

3+\mathrm{Ber}(8/27)

, and we give an almost complete proof.

2022

Graphe planaire

Ce graphe est clairement planaire, car il n'existe pas d'intersection entre deux arêtes.

C'est un graphe complet à quatre sommets (K4). Il est planaire : si on déplace le sommet 4 dans le triangle 1 2 3, on constate qu'il n'y a plus d'intersection d'arêtes.

C'est un graphe complet à 5 sommets (K5). Il n'est pas planaire.

C'est un graphe biparti complet K3,3 à 6 sommets, 3 d'entre eux se connectant aux trois autres.

An Maxflow Algorithm for Directed Planar Graphs

Modeling and Controlling epidemics : a graph perspective

On the robustness of the metric dimension of grid graphs to adding a single edge

Modeling and Controlling epidemics : a graph perspective

An Maxflow Algorithm for Directed Planar Graphs

On the robustness of the metric dimension of grid graphs to adding a single edge