An 
-permutation
graph of a labeled graph 
is the graph union of two disjoint
copies of 
on 
vertices, say 
and 
, together with edges joining
vertex 
of 
to vertex 
of 
, where 
is a permutation in the
symmetric group 
(Harary 1994, p. 175).
Skiena (1990, p. 28) defines a permutation graph 
as a graph whose edges 
correspond exactly to 
being a permutation
inversion in some permutation 
, i.e., 
but 
occurs before 
in 
. The above graph corresponds to the permutation 
, which has inverse
permutation 
.
