J. Gustedt, M. Morvan, L. Viennot A Compact Data Structure and Parallel Algorithms for Permutation Graphs Partant d'une permutation de {0,...,n-1}, on calcule en par­ allèle avec un travail en O(n log n) une structure de données de taille O(n log n). Cette structure de données permet d'obtenir efficacement le graphe associé à la permutation, la fermeture et la réduction transitive de l'ordre de dimension 2 correspondant. Les algorithmes parallèles obtenus ont un travail en O(m + n log n) où m représente le nombre d'arêtes du graphe. Tous les al­ gorithmes présentés s'exécutent en temps O(log2 n) sur une CREW PRAM. Starting from a permutation of {0,...,n-1} we compute in paral­ lel with a workload of O(n log n) a compact data structure of size O(n log n). This data structure allows to obtain the associ­ ated permutation graph and the transitive closure and reduction of the associated order of dimension 2 efficiently. The parallel algorithms obtained have a workload of O(m + n log n) where m is the number of edges of the permutation graph. They run in time O(log2 n) on a CREW PRAM.