Graphe médial

droite|vignette|500x500px|Un graphe planaire (en bleu) et son graphe médial (en rouge). En théorie des graphes, le graphe médial du graphe planaire G est un graphe M(G) qui représente les adjacences entre les côtés des faces de G. Les graphes médiaux ont été introduits en 1922 par Ernst Steinitz dans l'étude des propriétés combinatoires des polyèdres convexes, bien que la construction inverse ait déjà été utilisée par Peter Tait en 1877, dans son étude fondamentale des nœuds et entrelacs É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. droite|vignette|300x300px|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. 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.