Permutation graph
From Wikipedia, the free encyclopedia
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.
Contents[hide] |
[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.[1]
- A graph G is a permutation graph if and only if both G and it's complement are comparability graphs.[2]
[edit] Relation to other graph classes
[edit] Superclasses
- circle graph
- comparability graph
- co-comparability graph
[edit] Subclasses
- bipartite permutation graph
[edit] Notes
- ^ Brandstädt, Le & Spinrad (1999), Proposition 4.7.1, p.57.
- ^ Dushnik, & Miller (1941)
[edit] References
- 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 63 (3): 600–610, <http://www.jstor.org/stable/2371374>.