In areas of mathematics

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

 influenced by graph theory

Graph theory

In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

, a permutation graph is the intersection graph

Intersection graph

In the mathematical area of graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph may be represented as an intersection graph, but some important special classes of graphs may be defined by the types of sets that are used to form...

 of a family of line segments that connect two parallel

Parallel (geometry)

Parallelism is a term in geometry and in everyday life that refers to a property in Euclidean space of two or more lines or planes, or a combination of these. The assumed existence and properties of parallel lines are the basis of Euclid's parallel postulate. Two lines in a plane that do not...

 lines in the Euclidean plane. Equivalently, given a permutation

Permutation

In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order...

 (σ₁,σ₂,σ₃,...) of the numbers 1,2,3,...n, a permutation graph has a vertex for each number 1,2,3,...n and an edge between any two numbers that are in reversed order in the permutation i.e. an edge between any two numbers where the segments cross in the permutation diagram. A permutation graph has a unique representation as a permutation diagram if and only if it is prime with respect to the modular decomposition

Modular decomposition

In graph theory, the modular decomposition is a decomposition of an undirected graph into subsets of vertices called modules. A module is a generalization of a connected component of a graph. Unlike connected components, however, one module can be a proper subset of another...

.

Definition and characterization

• A graph G is a permutation graph if and only if G is a circle graph
  Circle graph
  In graph theory, a circle graph is the intersection graph of a set of chords of a circle. That is, it is an undirected graph whose vertices can be associated with chords of a circle such that two vertices are adjacent if and only if the corresponding chords cross each other.-Algorithmic...
  
   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
  Complement graph
  In graph theory, the complement or inverse of a graph G is a graph H on the same vertices such that two vertices of H are adjacent if and only if they are not adjacent in G. That is, to generate the complement of a graph, one fills in all the missing edges required to form a complete graph, and...
  
    are comparability graph
  Comparability graph
  In graph theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order...
  
  s.
• A graph G is a permutation graph if and only if it is the comparability graph
  Comparability graph
  In graph theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order...
  
   of a partially ordered set
  Partially ordered set
  In mathematics, especially order theory, a partially ordered set formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the...
  
   that has order dimension
  Order dimension
  In mathematics, the dimension of a partially ordered set is the smallest number of total orders the intersection of which gives rise to the partial order....
  
   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.

Efficient algorithms

As a subclass of the perfect graph

Perfect graph

In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the size of the largest clique of that subgraph....

s, many problems that are NP-complete

NP-complete

In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...

 for arbitrary graphs may be solved efficiently for permutation graphs. For instance:

• the largest clique
  Clique (graph theory)
  In the mathematical area of graph theory, a clique in an undirected graph is a subset of its vertices such that every two vertices in the subset are connected by an edge. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs...
  
   in a permutation graph corresponds to the longest decreasing subsequence
  Longest increasing subsequence
  The longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible...
  
   in the permutation defining the graph, so the clique problem
  Clique problem
  In computer science, the clique problem refers to any of the problems related to finding particular complete subgraphs in a graph, i.e., sets of elements where each pair of elements is connected....
  
   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
  Independent set
  In graph theory, an independent set or stable set is a set of vertices in a graph, no two of which are adjacent. That is, it is a set I of vertices such that for every two vertices in I, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in I...
  
   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.

Relation to other graph classes

Permutation graphs are a special case of circle graph

Circle graph

In graph theory, a circle graph is the intersection graph of a set of chords of a circle. That is, it is an undirected graph whose vertices can be associated with chords of a circle such that two vertices are adjacent if and only if the corresponding chords cross each other.-Algorithmic...

s, comparability graph

Comparability graph

In graph theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order...

s, the complements of comparability graphs, and trapezoid graphs

Trapezoid graph

In graph theory, trapezoid graphs are intersection graphs of trapezoids between two horizontal lines. They are a class of co-comparability graphs that contain interval graphs and permutation graphs as subclasses...

.

The subclasses of the permutation graphs include the bipartite

Bipartite graph

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...

 permutation graphs and the cograph

Cograph

In graph theory, a cograph, or complement-reducible graph, or P4-free graph, is a graph that can be generated from the single-vertex graph K1 by complementation and disjoint union...

s.