Перестановочный граф

Перестановочный граф (Permutation graph) — граф пересечений сегментов в диаграмме пересечений перестановки; для построений последней возьмем по $\,n$ точек на двух параллельных прямых и соединим прямолинейными отрезками пары точек согласно биекции определяемой перестановкой.

Литература

• Golumbic M.C. Algorithmic graph theory and perfect graphs. — New York: Academic Press, 1980.