Encyclopedia

Permutation graph

Graph representing a permutation

Wikipedia contributorsAdapted for Fathomly · View authors

3 min read
Source updated August 10, 2026

In the mathematical field of graph theory, a permutation graph is a graph whose vertices represent the elements of a permutation, and whose edges represent pairs of elements that are reversed by the permutation. Permutation graphs may also be defined geometrically, as the intersection graphs of line segments whose endpoints lie on two parallel lines. Different permutations may give rise to the same permutation graph; a given graph has a unique representation (up to permutation symmetry) if it is prime with respect to the modular decomposition.

01Definition and characterization

If $\rho =(\sigma _{1},\sigma _{2},...,\sigma _{n})$ is any permutation of the numbers from $1$ to $n$ , then one may define a permutation graph from $\sigma$ in which there are $n$ vertices $v_{1},v_{2},...,v_{n}$ , and in which there is an edge $v_{i}v_{j}$ for any two indices $i<j$ for which $j$ appears before $i$ in $\rho$ . That is, two indices $i$ and $j$ determine an edge in the permutation graph exactly when they determine an inversion in the permutation.

Given a permutation $\sigma$ , one may also determine a set of line segments $s_{i}$ with endpoints $(i,0)$ and $(k,1)$ , such that $\sigma _{k}=i$ . The endpoints of these segments lie on the two parallel lines $y=0$ and $y=1$ , and two segments have a non-empty intersection if and only if they correspond to an inversion in the permutation. Thus, the permutation graph of $\sigma$ coincides with the intersection graph of the segments. For every two parallel lines, and every finite set of line segments with endpoints on both lines, the intersection graph of the segments is a permutation graph; in the case that the segment endpoints are all distinct, a permutation for which it is the permutation graph may be given by numbering the segments on one of the two lines in consecutive order, and reading off these numbers in the order that the segment endpoints appear on the other line.

Permutation graphs have several other equivalent characterizations:

A graph $G$ is a permutation graph if and only if $G$ is a circle graph that admits an equator, i.e., an additional chord that intersects every other chord.
A graph $G$ is a permutation graph if and only if both $G$ and its complement ${\overline {G}}$ are comparability graphs.
A graph $G$ is a permutation graph if and only if it is the comparability graph of a partially ordered set that has order dimension at most two.
If a graph $G$ is a permutation graph, so is its complement. A permutation that represents the complement of $G$ may be obtained by reversing the permutation representing $G$ .

02Efficient algorithms

It is possible to test whether a given graph is a permutation graph, and if so construct a permutation representing it, in linear time.

As a subclass of the perfect graphs, many problems that are NP-complete for arbitrary graphs may be solved efficiently for permutation graphs. For instance:

the largest clique in a permutation graph corresponds to the longest decreasing subsequence in the permutation defining the graph, so the clique problem may be solved in polynomial time for permutation graphs by using a longest decreasing subsequence algorithm.
likewise, an increasing subsequence in a permutation corresponds to an independent set of the same size in the corresponding permutation graph.
the treewidth and pathwidth of permutation graphs can be computed in polynomial time; these algorithms exploit the fact that the number of inclusion minimal vertex separators in a permutation graph is polynomial in the size of the graph.

03Relation to other graph classes

Permutation graphs are a special case of circle graphs, comparability graphs, the complements of comparability graphs, and trapezoid graphs.

The subclasses of the permutation graphs include the bipartite permutation graphs (characterized by Spinrad, Brandstädt & Stewart 1987) and the cographs.

Watch videos about Permutation graphExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Permutation graph”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Images, from Wikimedia Commons:

Permutation graph.svg by Lyonsam, Public domain

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.