  We present a succinct data structure for permutation graphs, and their
superclass of circular permutation graphs, i.e., data structures using optimal
space up to lower order terms. Unlike concurrent work on circle graphs (Acan et
al. 2022), our data structure also supports distance and shortest-path queries,
as well as adjacency and neighborhood queries, all in optimal time. We present
in particular the first succinct exact distance oracle for (circular)
permutation graphs. A second succinct data structure also supports degree
queries in time independent of the neighborhood's size at the expense of an
$O(\log n/\log \log n)$-factor overhead in all running times. Furthermore, we
develop a succinct data structure for the class of bipartite permutation
graphs. We demonstrate how to run algorithms directly over our succinct
representations for several problems on permutation graphs: Clique, Coloring,
Independent Set, Hamiltonian Cycle, All-Pair Shortest Paths, and others.
  Finally, we initiate the study of semi-distributed graph representations; a
concept that smoothly interpolates between distributed (labeling schemes) and
centralized (standard data structures). We show how to turn some of our data
structures into semi-distributed representations by storing only $O(n)$ bits of
additional global information, circumventing the lower bound on distance
labeling schemes for permutation graphs.
