In the
mathematical
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
field of
graph theory
In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
, a permutation graph is a
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discret ...
whose
vertices represent the elements of a
permutation
In mathematics, a permutation of a set can mean one of two different things:
* an arrangement of its members in a sequence or linear order, or
* the act or process of changing the linear order of an ordered set.
An example of the first mean ...
, 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
Symmetry () in everyday life refers to a sense of harmonious and beautiful proportion and balance. In mathematics, the term has a more precise definition and is usually used to refer to an object that is Invariant (mathematics), invariant und ...
) if it is
prime
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
with respect to the
modular decomposition
In Graph (discrete mathematics), graph theory, the modular decomposition is a decomposition of a Graph (discrete mathematics), graph into subsets of Vertex (graph theory), vertices called modules. A ''module'' is a generalization of a Connected c ...
.
Definition and characterization
If
is any
permutation
In mathematics, a permutation of a set can mean one of two different things:
* an arrangement of its members in a sequence or linear order, or
* the act or process of changing the linear order of an ordered set.
An example of the first mean ...
of the numbers from
to
, then one may define a permutation graph from
in which there are
vertices , and in which there is an edge
for any two indices
for which
appears before
in
. That is, two indices
and
determine an edge in the permutation graph exactly when they determine an
inversion in the permutation.
Given a permutation
, one may also determine a set of
line segment
In geometry, a line segment is a part of a line (mathematics), straight line that is bounded by two distinct endpoints (its extreme points), and contains every Point (geometry), point on the line that is between its endpoints. It is a special c ...
s
with endpoints
and
, such that
. The endpoints of these segments lie on the two parallel lines
and
, 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
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
is a permutation graph if and only if
is a
circle graph
In graph theory, a circle graph is the intersection graph of a Chord diagram (mathematics), chord diagram. That is, it is an undirected graph whose vertices can be associated with a finite system of Chord (geometry), chords of a circle such tha ...
that admits an ''equator'', i.e., an additional
chord that intersects every other chord.
*A graph
is a permutation graph if and only if both
and its
complement are
comparability graph
In graph theory and order theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order. Comparability graphs have also been called transitively orientable graphs, partial ...
s.
*A graph
is a permutation graph if and only if it is the
comparability graph
In graph theory and order theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order. Comparability graphs have also been called transitively orientable graphs, partial ...
of a
partially ordered set
In mathematics, especially order theory, a partial order on a Set (mathematics), set is an arrangement such that, for certain pairs of elements, one precedes the other. The word ''partial'' is used to indicate that not every pair of elements need ...
that has
order dimension at most two.
*If a graph
is a permutation graph, so is its complement. A permutation that represents the complement of
may be obtained by reversing the permutation representing
.
Efficient 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
In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations ...
.
As a subclass of the
perfect graph
In graph theory, a perfect graph is a Graph (discrete mathematics), graph in which the Graph coloring, chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic nu ...
s, many problems that are
NP-complete
In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''.
Somewhat more precisely, a problem is NP-complete when:
# It is a decision problem, meaning that for any ...
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
In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...
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
In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests
...
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
In graph theory, a circle graph is the intersection graph of a Chord diagram (mathematics), chord diagram. That is, it is an undirected graph whose vertices can be associated with a finite system of Chord (geometry), chords of a circle such tha ...
s,
comparability graph
In graph theory and order theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order. Comparability graphs have also been called transitively orientable graphs, partial ...
s, the complements of comparability graphs, and
trapezoid graphs.
The subclasses of the permutation graphs include the
bipartite permutation graphs (characterized by ) and the
cographs.
Notes
References
*.
*.
*.
*.
*.
*.
*.
External links
*
* {{mathworld, id=PermutationGraph, title=Permutation Graph, mode=cs2
Intersection classes of graphs
Perfect graphs
Geometric graphs