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 permutation123,...) 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]

[edit] Relation to other graph classes

[edit] Superclasses

[edit] Subclasses

  • bipartite permutation graph

[edit] Notes

[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 .

[edit] External links