置換グラフ

σ = (σ₁,σ₂, ..., σ_n) を 1から n までの置換とすると、 n 頂点（v₁, v₂, ..., v_n）の置換グラフを定義できる。 i < j であり σ_i > σ_jであるとき、 v_iv_j に辺を有するグラフが置換グラフとなる。つまり、 i と j の大小関係が入れ替わっているような組に対して、置換グラフは辺を有する。 置換σが与えられると、( i, 0) から (σ_i, 1)へと伸びる線分 s_iが定義できる。 線分の端点は2本の平行な線 y = 0 （置換前）と y = 1 （置換後）上にあり、2つの要素が順列の反転に対応する場合に限り、交点が生じる。したがって、σの置換グラフは要素の交差グラフと一致する。線分の終点が全て異なる場合、置換グラフで定義された置換は、2つの線のうちの1つの線上のセグメントに連続した番号を付け（図中の上の12345）、もう一方の線上での、線分のもう一方の端点の数字が置換後の数列（43512）となる。

置換グラフは、以下のような同値な特徴を持つ。 グラフ G が置換グラフであれば、そしてその時に限り

• G はcircle graphであり、他のすべての弦と交差する追加の弦「赤道」を認める^[2]。
• G とその補グラフ${\displaystyle {\overline {G}}}$ が「比較可能グラフ」である^[3]。
• 高々2のorder dimension を持つ半順序集合の比較可能グラフ比較可能グラフである^[4]。

グラフ G が置換グラフであれば

• 補グラフも置換グラフである。

与えられたグラフが置換グラフであるかを判定し、もし置換グラフであればその置換を導出する処理は、線形時間で処理可能である^[5]。

一般のグラフに対してはNP完全であるような問題に対しても、入力が置換グラフであれば、パーフェクトグラフの一種として、効率的なアルゴリズムが存在する場合がある。

• 置換グラフの最大クリークはグラフを定義する順列の最長増加（減少）部分列に対応するため、最長増加（減少）部分列を導出するアルゴリズムを使用して、置換グラフの最大クリーク問題を多項式時間で解くことが可能^[6]。
• 同様に、置換において増加部分列は、対応する置換グラフにおける同じサイズの独立集合に対応する。
• 置換グラフの木幅 と パス幅 は多項式時間で計算できる。そのアルゴリズムは、頂点分離の数がグラフのサイズの多項式で表されることに由来する^[7]。

• 置換グラフはcircle graphの特殊な例である。
• 置換グラフは比較可能グラフの特殊な例である。
• 置換グラフは比較可能グラフの補グラフの特殊な例である。
• 置換グラフは台形グラフの特殊な例である。

置換グラフは2部グラフやcographなどの派生がある（詳しくは ^[8] を参照）。