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

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

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

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

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

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

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

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