Хорошее стягивающее деревоШаблон:Sfn <math>T</math> вложенного планарного графа <math>G</math> — это корневое остовное дерево графа <math>G</math>, не принадлежащие дереву рёбра которого удовлетворяют следующим условиям:
нет не принадлежащего дереву ребра <math>(u,v)</math>, в котором вершины <math>u</math> и <math>v</math> лежат на пути из корня дерева <math>T</math> в лист,
рёбра, инцидентные вершине <math>v</math>, могут быть разбиты на три множества <math>X_v, Y_v </math> и <math> Z_v</math>, где
<math>X_v</math> является множеством не принадлежащих дереву рёбер, они определяют красную зону
<math>Y_v</math> является множеством рёбер дерева, они являются детьми вершины <math>v</math>
<math>Z_v</math> является множеством не принадлежащих дереву рёбер, они определяют зелёную зону
Файл:GST conditions.svgИллюстрация множеств рёбер <math>X_v , Y_v </math> и <math>Z_v</math>
Пусть <math>G_\phi</math> будет планарным графом. Пусть <math>T</math> будет корневым стягивающим деревом графа <math>G_\phi</math>. Пусть <math>P(r,v)=(r=u_1), u_2, \ldots, (v=u_k)</math> будет путём в <math>T</math> от корня <math>r</math> к вершине <math>v\ne r</math>. Путь <math>P(r,v)</math> делит детей <math>u_i</math>, <math>(1\leqslant i < k)</math>, за исключением <math>u_{i+1}</math>, на две группы. Левую группу <math>L</math> и правую группу <math>R</math>. Дочерняя вершина <math>x</math> вершины <math>u_i</math> находится в группе <math>L</math> и обозначается как <math>u_{i}^L</math>, если ребро <math>(u_i,x)</math> появляется до ребра <math>(u_i, u_{i+1})</math> при упорядочении по часовой стрелке рёбер, инцидентных <math>u_i</math>, если упорядочение начинается с <math>(u_i,u_{i+1})</math>. Аналогично, дочерняя вершина <math>x</math> вершины <math>u_i</math> находится в группе <math>R</math> и обозначается как <math>u_{i}^R</math>, если ребро <math>(u_i,x)</math> появляется после ребра <math>(u_i, u_{i+1})</math> в упорядочении по часовой стрелке рёбер, инцидентных <math>u_i</math>, если упорядочение начинается с ребра <math>(u_i,u_{i+1})</math>. Дерево <math>T</math> называется хорошим стягивающим деревомШаблон:Sfn графа <math>G_\phi</math>, если любая вершина <math>v</math> <math>(v\ne r)</math> графа <math>G_\phi</math> удовлетворяет двум условиям по отношению к <math>P(r,v)</math>.
[Условие 1] <math>G_\phi</math> не содержит не принадлежащего дереву ребра <math>(v,u_i)</math>, <math>i<k</math>
[Условие 2] рёбра графа <math>G_\phi</math>, инцидентные вершине <math>v</math>, исключая <math>(u_{k-1},v)</math>, могут быть разбиты на три непересекающиеся (возможно пустых) множества <math>X_v,Y_v</math> и <math>Z_v</math>, удовлетворяющих условиям (a)-(c)
(a) Каждое из множеств <math>X_v</math> и <math>Z_v</math> является множеством не принадлежащих дереву рёбер, а <math>Y_v</math> является множеством рёбер дерева.
(b) Рёбра множеств <math>X_v</math>, <math>Y_v</math> и <math>Z_v</math> появляются по часовой стрелке в этом порядке от ребра <math>(u_{k-1}, v)</math>.
(c) Для каждого ребра <math>(v,v')\in X_v</math>, <math>v'</math> содержится в <math>T_{u_i^L}</math> <math>i<k</math>, а для каждого ребра <math>(v,v')\in Z_v</math>, <math>v'</math> содержится в <math>T_{u_i^R}</math> <math>i<k</math>.Файл:Good spanning tree example.svgПланарный граф <math>G_\phi</math> (сверху), хорошее стягивающее дерево <math>T</math> графа <math>G_\phi</math> (внизу), сплошные рёбра являются частями хорошего стягивающего дерева, а пунктирные рёбра не принадлежат дереву <math>T</math>.
Приложения
Применяется в мнототонном рисовании графовШаблон:Sfn и в прямоугольном представлении графовШаблон:Sfn[1].
Поиск хорошего стягивающего дерева
Любой планарный граф <math>G</math> имеет вложение <math>G_\phi</math>, такое, что <math>G_\phi</math> содержит хорошее стягивающее дерево. Хорошее стягивающее дерево и подходящее вложение могут быть найдены для графа <math>G</math> за линейное времяШаблон:Sfn. Не все вложения графа <math>G</math> содержат хорошее стягивающее дерево.
↑На английском - 2-visibility representation. В этом представлении графа вершины представлены прямоугольниками, а рёбра (связи) представлены горизонтальными и вертикальными линиями Шаблон:Harv
