En théorie des graphes, un graphe de permutation est un graphe non orienté dont les sommets représentent les éléments d'une permutation, et dont les arêtes relient les paires de sommets qui sont inversés dans la permutation. On peut aussi définir les graphes de permutations de manière géométrique : ce sont les graphes d'intersections de segments dont les extrémités sont sur deux droites parallèles.
On définit les graphes de permutation de la manière suivante. Les sommets représentent les éléments d'une permutation, et les arêtes relient les paires de sommets dont les éléments sont inversés dans la permutation.
Autre caractérisations :
La classe des graphes de permutation est incluse dans les graphes de comparabilité, dans les circle graphs, et dans les graphes trapézoïdaux (en).
Les cographes sont des graphes de permutation.
