弦グラフ
この分割を繰り返し、全ての頂点を一度ずつ選び終わったとき、perfect elimination orderingの逆の順に並ぶ。
lexicographic breadth first searchと、出力された順序がperfect elimination orderingかを確かめる処理は両方とも線形時間であるため、弦グラフに対して線形時間で処理可能である。弦グラフに対するprobe graph problemは多項式時間で解ける一方、弦グラフに対するGraph sandwich problemはNP完全である。
弦グラフに対する全てのperfect elimination ordering集合は反マトロイド(antimatroid)の基としてモデル化できる。例えば、Chandran et al. (2003)は与えられた弦グラフの全てのperfect elimination orderingsを効率的に列挙するアルゴリズムの一部として、反マトロイドへのこの接続を使いた。