HOME

TheInfoList



OR:

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 \rho = (\sigma_1,\sigma_2,...,\sigma_n) 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 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 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 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 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 G is a permutation graph if and only if both G and its complement \overline 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 G 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 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

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