User Tools

Site Tools


chicoutimi_2016:graphes_planaires

Visual Analytics Course

Instructor: Guy Melançon (email: Guy dot Melancon at labri dot fr)

Chicoutimi Summer 2016 roadmap / Session by session cutdown

Graphes planaires

Les graphes planaires sont l'archétype des graphes lisibles: leurs arêtes ne se chevauchent pas. Les cartes géographiques sont des graphes planaires (si on considère les liens entre pays transfrontaliers).

L'exemple de la figure est un graphe planaire – (et un peu plus, puisque ses arêtes sont routées sur une grille).

Les graphes planaires sont des objets combinatoires des plus intéressants.

Un graphe planaire a nécessairement peu d'arêtes. Combien ?

Formule d'Euler. Pour tout graphe planaire connexe:

où est son nombre de sommets, est son nombre d'arêtes et son nombre de faces (face extérieure incluse).

Démonstration. On procède par récurrence sur le nombre d'arêtes du graphe. Puisqu'il est supposé connexe, on a par conséquent .

S'il n'y a pas de cycle dans le graphe, c'est un arbre, il possède une unique face (la face extérieure) et la formule d'Euler est valide puisque .

Supposons donc que le graphe admet un cycle, auquel on supprime momentanément une arête. Ce graphe est planaire avec un nombre d'arêtes . Par conséquent, il satisfait la formule d'Euler où sont ses nombre de sommets, d'arêtes et de faces. Or, on a f' = f - 1$ (puisqu'on a “brisé” un cycle). Ainsi,

Proposition. Le nombre d’arêtes d’un graphe connexe et planaire (et qui n’est pas un arbre) est où est la longueur de son pus court cycle.

Démonstration. Soit le graphe admet un isthme:

Puisque l'inégalité tient sur chacun des deux sous-graphes reliés par l'isthme:

puisque .

Si le graphe n'admet pas d'isthme, chaque arête est incidente à deux faces du graphes (face extérieure incluse):

où est le nombre de faces cernées par un cycle de longueur . On applique la formule d'Euler () et on trouve le résultat.

Par conséquent, un graphe planaire admet au plus arêtes (où est son nombre de sommets) puisque le cycle le plus court est de longueur au moins 3.

Test de planarité. Il est intéressant de pouvoir tester si un graphe est planaire – ce test ne fournit pas un dessin du graphe mais établit si le graphe admet un dessin planaire.

On possède déjà un critère pour répondre négativement (si le nombre d'arêtes est trop grand).

Un graphe est planaire si (et seulement si) toutes ses composantes connexes le sont. On supposera donc le graphe connexe par la suite. Un graphe connexe est planaire si et seulement si tous ses blocs sont planaires.

Un bloc est une composante biconnexe d'un graphe (connexe), c'est une sous-graphe maximal dans lequel il existe, pour toute paire de sommets , deux chemins distincts.

Un sommet est un point d'articulation si après suppression le graphe n'est pus connexe.

On peut trouver dans un graphe les points d'articulations, ce sont les sommets de degré sortant au moins 2 dans un arbre couvrant obtenu d'un parcours en profondeur du graphe.

On peut donc supposer être face à un graphe connexe et biconnexe. Un dessin planaire d'un graphe s'obtient par assemblage d'un dessin planaire de chacun des blocs (et de chacune de ses composantes connexes).

Pièces d'un graphe (biconnexe). On suppose l'existence d'un cycle dans le graphe (un graphe biconnexe possède nécessairement un cycle). On partage les arêtes du graphe en classe: deux arêtes appartiennent à une même classe s'il existe un chemin ne passant pas par le cycle les contenant toutes deux.

Le graphe biconnexe de la figure contient 6 pièces.

Les pièces ont des points d'ancrage sur le cycle: des sommets de la classe qui sont sur le cycle. On peut donc établir si deux pièces s'entrelacent.

De deux pièces qui s’entrelacent :

  • L’une doit être dessiné à l’intérieur du cycle
  • L’autre doit être dessiné à l’extérieur

Comment décider s’il est possible d’appliquer ce principe de manière cohérente à l’ensemble des pièces ? Les pièces sont les sommets d’un “nouveau” graphe: deux pièces y sont adjacentes si elles s’entrelacent. Par construction,

Le graphe est planaire ssi le graphe d’entrelacement des pièces est biparti

  • Une pièce à l’intérieur, puis une à l’extérieur, …

/net/html/perso/melancon/Visual_Analytics_Course/data/pages/chicoutimi_2016/graphes_planaires.txt · Last modified: 2016/05/05 17:16 by melancon