K-дерево

k-Деревья — это в точности максимальные графы с заданной древесной шириной, то есть графы, к которым нельзя добавить ребро без увеличения древесной ширины графа[2]. Это также в точности хордальные графы, все максимальные клики которых имеют один и тот же размер ${\displaystyle k+1}$ и все минимальные кликовые сепараторы которых имеют также одинаковый размер k[1].

1-Деревья — это то же самое, что и некорневые деревья. 2-деревья являются максимальными параллельно-последовательными графами[3], и они включают также максимальные внешнепланарные графы. Планарные 3-деревья известны также как сети Аполлония[4].

Графы, которые имеют древесную ширину, не превосходящую k, это в точности подграфы k-деревьев, и по этой причине они называются частичными k-деревьями[2].

Графы, образованные рёбрами и вершинами k-мерных блоковых многогранников, то есть многогранников, образованных, начиная с симплекса, последовательным склеиванием граней симплексов, являются k-деревьями, если ${\displaystyle k\geqslant 3}$[5]. Этот процесс склеивания имитирует построение k-деревьев путём добавления вершин в клику[6]. k-Дерево является графом блокового многогранника тогда и только тогда, когда никакие три клики с (k + 1) вершинами не имеют k общих вершин [7].