Graphe médial

Étant donné un graphe planaire G, son graphe médial M(G) est le graphe dont les sommets sont les arêtes de G, deux sommets étant reliés si les arêtes de G correspondantes sont consécutives dans une de ses faces. Le graphe médial est donc un sous-graphe du line graph L(G).

La notion de graphe médial s'étend aux graphes plongés dans des surfaces de genre quelconque.

Les deux graphes rouges sont tous les deux graphes médiaux du graphe bleu, mais ils ne sont pas isomorphe.

• Le graphe médial d'un graphe planaire est lui aussi planaire, et de plus ses sommets sont d'ordre 4 (il est 4-régulier).
• Le graphe médial de G et celui de son dual sont isomorphes. Inversement, pour tout graphe planaire 4-régulier H, il existe exactement deux graphes planaires ayant H pour graphe médial et ces deux graphes sont duaux l'un de l'autre[5].
• Comme le graphe médial est associé à un plongement particulier du graphe G, deux plongements différents peuvent donner naissance à des graphes médiaux non isomorphes. Dans la représentation ci-contre, les deux graphes médiaux rouges ne sont pas isomorphes car les deux sommets à boucles sont reliés par une arête dans l'un, et pas dans l'autre.
• Pour obtenir l'un des deux graphes G dont H est le médial, colorier les faces de H avec deux couleurs, ce qui est possible puisque H est eulérien (et donc le graphe dual de H est biparti). Les sommets de G correspondent aux faces d'une couleur donnée. Ces sommets sont reliés par une arête si les faces correspondantes ont un sommet en commun dans H. Notons que l'exécution de cette construction à l'aide des faces de l'autre couleur que la couleur choisie produit le graphe dual de G.

Pour un graphe planaire G, le double de la valeur du polynôme de Tutte au point (3,3) est égal à la somme des orientations eulériennes pondérées dans le graphe médial de G, où le poids d'une orientation est entre 2 et le nombre de sommets de l'orientation (c'est-à-dire le nombre de sommets dont les arêtes incidentes sont cycliquement ordonnées «in, out, in out»)[6]. Puisque le polynôme de Tutte est invariant par plongement, ce résultat montre que chaque graphe médial a la même somme des orientations eulériennes pondérées.

Un graphe planaire (en bleu) et son graphe médial orienté (en rouge).

La définition du graphe médial peut être étendue de sorte à inclure une orientation. Tout d'abord, on colorie les faces du graphe médial en noir si elles contiennent un sommet du graphe originel et en blanc sinon. Cette coloration fait que chaque arête du graphe médial est bordée par une face noire et une face blanche. Ensuite, chaque arête est orientée de telle sorte que la face noire soit sur sa gauche.

Un graphe planaire et son dual n'ont pas le même graphe médial orienté ; ils sont transposés l'un de l'autre.

En utilisant le graphe médial orienté, on peut généraliser le résultat sur l'évaluation du polynôme de Tutte en (3,3). Pour un graphe planaire G , la valeur du polynôme de Tutte au point ( n + 1, n + 1) multipliée par n donne la somme pondérée sur toutes les colorations d'arêtes en utilisant n couleurs dans le graphe médial orienté de G, de sorte que chaque ensemble (éventuellement vide) d'arêtes monochromatiques forme un graphe orienté eulérien, où le poids d'une orientation d'Euler est entre 2 et le nombre de sommets monochromatiques[7].

• Line graph
• Entrelacs et graphes