Укладка дерева

Дерево — планарный граф. Согласно следствию из формулы Эйлера: для дерева с [math]N[/math] вершинами [math]N - 1 \le 3 \cdot N - 6[/math].

Укладка дерева

Существуют несколько способов укладки дерева на плоскости.

Поуровневая укладка

Простой способ построения нисходящего плоского изображения дерева заключается в использовании его поуровневого расположения, при котором вершины глубины [math]a[/math] имеют координату [math]y = – a[/math], а координаты по горизонтальной оси распределяются так, чтобы никакие левые поддеревья не пересекались с правыми. Возможна реализация за линейное время, позволяющая получить оптимальное по ширине плоское дерево в области размера [math]O(N^2)[/math] (где [math]N[/math] — число вершин дерева).

Радиальная поуровневая укладка

Радиальная поуровневая укладка дерева отличается тем, что его уровни имеют вид концентрических окружностей, поддеревья занимают секторные сегменты.

Выбор угла [math]\beta_p[/math] секторного сегмента для поддерева с корнем [math]p[/math] и количеством вершин [math]l(p)[/math] определяется следующим образом: пусть вершина [math]p[/math] лежит на уровне [math]C_i[/math], тогда для каждого ее сына [math]q[/math] имеем: [math]\beta_q = \min(\frac{l(q)\beta_p}{l(p)}, \tau)[/math], где [math]\tau[/math] — это угол области [math]F_p[/math], определяемой пересечением касательной к точке [math]p[/math] уровня [math]C_i[/math] и окружностью уровня [math]C_{i+1}[/math].

Радиальное изображение дерева часто используют для представления свободных деревьев, причем в качестве вершины, размещаемой в центре, берется одна из его центральных вершин.

hv-изображения

Для hv-изображения дерева для каждой вершины [math]p[/math] выполняются следующие свойства:

• сын вершины [math]p[/math] ставится в ряд за [math]p[/math] либо по горизонтали справа, либо по вертикали вниз;
• не пересекаются минимальные прямоугольники с горизонтальными и вертикальными вершинами, покрывающие поддеревья вершины [math]p[/math].