Permutation graph
In areas of mathematics influenced by graph theory, a permutation graph is the intersection graph of a family of line segments that connect two parallel lines in the Euclidean plane. Equivalently, given a permutation (σ1,σ2,σ3,...) 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.[1]
Contents |
[edit] Definition and characterization
- 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.[2]
- A graph G is a permutation graph if and only if both G and its complement
are comparability graphs.[3] - 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.[4]
- 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.
are [edit] Efficient algorithms
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.[5]
- 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.[6]
[edit] Relation 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 and the cographs.
[edit] Notes
- ^ Brandstädt, Le & Spinrad (1999), p.191.
- ^ Brandstädt, Le & Spinrad (1999), Proposition 4.7.1, p.57.
- ^ Dushnik, & Miller (1941).
- ^ Baker, Fishburn & Roberts (1971).
- ^ Golumbic (1980).
- ^ Bodlaender, Kloks & Kratsch (1995)
[edit] References
- Baker, K. A.; Fishburn, P.; Roberts, F. S. (1971), "Partial orders of dimension 2", Networks 2 (1): 11–28, doi:10.1002/net.3230020103.
- Bodlaender, Hans L.; Kloks, Ton; Kratsch, Dieter (1995). "Treewidth and Pathwidth of Permutation Graphs". SIAM Journal on Discrete Mathematics 8: 606–616. doi:10.1137/S089548019223992X.
- Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy (1999), Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-432-X.
- Dushnik, Ben; Miller, E. W. (1941), "Partially ordered sets", American Journal of Mathematics (The Johns Hopkins University Press) 63 (3): 600–610, doi:10.2307/2371374, JSTOR 2371374.
- Golumbic, M. C. (1980), Algorithmic Graph Theory and Perfect Graphs, Computer Science and Applied Mathematics, Academic Press, p. 159.
