A Compact Data Structure and Parallel Algorithms for Permutation Graphs

. Starting from a permutation of f0; : : : ; n \Gamma 1g we compute in parallel 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 associated 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(log 2 n) on a CREW PRAM. 1 Introduction Permutation graphs are combinatorial objects that found a lot of attention in recent years. This interest led to many results under a structural point of view as well as algorithmically, see [1, 2, 6, 7, 8]. By definition permutation graphs have a compact encoding of size n, where n is the number of vertices. In sequential computing model, it is possible to pass from the graph to the permutation and vice versa with a workload of O(n 2 ). For parallel computing this has been open up to no..