For a permutation 
in the symmetric group 
, the 
-permutation graph of a labeled
graph 
is the graph union of two disjoint copies of 
(say, 
and 
), together with the lines joining point 
of 
with 
of 
(Harary 1994, p. 175).
Skiena (1990, p. 28) defines a permutation graph 
as a graph whose edges 
correspond exactly to 
being a permutation
inversion is some permutation 
, i.e., 
but 
occurs before 
in 
. The above graph corresponds to the permutation 
, which has permutation
inversion 
.
Permutation graphs are implemented as PermutationGraph[p]
in the Wolfram Language package Combinatorica`
.
