置換グラフ
与えられたグラフが置換グラフであるかを判定し、もし置換グラフであればその置換を導出する処理は、線形時間で処理可能である。
一般のグラフに対してはNP-完全であるような問題に対しても、入力が置換グラフであれば、パーフェクトグラフの一種として、効率的なアルゴリズムが存在する場合がある。
置換グラフの最大クリークはグラフを定義する順列の最長増加(減少)部分列に対応するため、最長増加(減少)部分列を導出するアルゴリズムを使用して、置換グラフの最大クリーク問題を多項式時間で解くことが可能。
同様に、置換において増加部分列は、対応する置換グラフにおける同じサイズの独立集合に対応する。
置換グラフの木幅 と パス幅 は多項式時間で計算できる。そのアルゴリズムは、頂点分離の数がグラフのサイズの多項式で表されることに由来する。