Permutation graph

In graph-theoretic mathematics, a permutation graph is the intersection graph of a family of line segments that connect two parallel lines in the Euclidean plane.

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.

• A graph G is a permutation graph if and only if both G and it's complement ${\overline {G}}$ are comparability graphs.

Relation to other graph classes

Superclasses

• circle graphs.
• comparability graphs
• co-comparability graphs

Subclasses

• bipartite permutation graphs

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.

External links

• "permutation graph". Information System on Graph Class Inclusions. {{cite web}}: External link in |work= (help)