弦グラフ
任意のグラフGの弦化とは、Gを部分グラフとして持つような弦グラフである。最小弦化は複数のパラメータに従う計算複雑性を持ち、準指数時間で解くことができる。 Gの木幅はクリークのサイズが最小となるような弦化が施されたGの最大クリークの頂点数-1である。 k-木は木幅をkより大きくしなければ辺を追加できないグラフである。したがって、k-木はそれ自身の弦化であり、弦グラフの一種である。弦化は他のグラフの特徴付にも使われる。
perfect elimination orderingとは、「隣接する頂点集合がクリークを形成しているグラフの頂点 v の削除」を繰り返し、グラフ全体が削除されるような順序付けである。グラフが弦グラフであれば、そしてその時に限りグラフはperfect elimination orderingを持つ。
Rose, Lueker & Tarjan (1976) (see also Habib et al. 2000) は、Lexicographic Breadth First Search と呼ばれる辞書順に並べながら探索する手法で、効率的に弦グラフのperfect elimination orderingが見つかると示した。このアルゴリズムは、グラフの頂点を集合列に以下の手法で分割する。 まず、全ての頂点を含む1つの集合を考える。そして、一度も選ばれていない頂点を含む最初の集合 S から頂点 v を選び、S を「v に隣接している頂点」と「v に隣接していない頂点」の2つの集合に分割する。
1974年、Gavrilによって、部分木を用いた弦グラフの異なる定義が用いられた。
木の部分木の集合から、部分木ごとに1つの頂点と重複する2つの部分木を持つ交差グラフである「部分木グラフ」を定義できる。この「部分木グラフ」は弦グラフであることをGavrilは証明した。
部分木の交差として弦グラフを表すと、グラフの木幅がグラフ内の最大クリークのサイズより1小さい、木分解が生成される。任意のグラフG の木分解は弦グラフの部分グラフとしてGを表現したものとして捉えられる。グラフの木分解は、Junction tree algorithmの木分解でもある。