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. A permutation graph has a unique representation if and only if it is prime with respect to the split 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]
[edit] Relation to other graph classes
[edit] Superclasses
[edit] Subclasses
[edit] Notes
- ^ Brandstädt, Le & Spinrad (1999), p.191.
- ^ 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.
