Хорошее стягивающее дерево вложенного планарного графа — это корневое остовное дерево графа , не принадлежащие дереву рёбра которого удовлетворяют следующим условиям: нет не принадлежащего дереву ребра , в котором вершины и лежат на пути из корня дерева в лист, рёбра, инцидентные вершине , могут быть разбиты на три множества и , где является множеством не принадлежащих дереву рёбер, они определяют красную зону является множеством рёбер дерева, они являются детьми вершины является множеством не принадлежащих дереву рёбер, они определяют зелёную зону
Формальное определение
Пусть будет планарным графом. Пусть будет корневым стягивающим деревом графа . Пусть будет путём в от корня к вершине . Путь делит детей , , за исключением , на две группы. Левую группу и правую группу . Дочерняя вершина вершины находится в группе и обозначается как , если ребро появляется до ребра при упорядочении по часовой стрелке рёбер, инцидентных , если упорядочение начинается с . Аналогично, дочерняя вершина вершины находится в группе и обозначается как , если ребро появляется после ребра в упорядочении по часовой стрелке рёбер, инцидентных , если упорядочение начинается с ребра . Дерево называется хорошим стягивающим деревом графа , если любая вершина графа удовлетворяет двум условиям по отношению к .
[Условие 1] не содержит не принадлежащего дереву ребра , [Условие 2] рёбра графа , инцидентные вершине , исключая , могут быть разбиты на три непересекающиеся (возможно пустых) множества и , удовлетворяющих условиям (a)-(c) (a) Каждое из множеств и является множеством не принадлежащих дереву рёбер, а является множеством рёбер дерева. (b) Рёбра множеств , и появляются по часовой стрелке в этом порядке от ребра . (c) Для каждого ребра , содержится в , а для каждого ребра , содержится в .
Приложения Применяется в мнототонном рисовании графов и в прямоугольном представлении графовНа английском - 2-visibility representation. В этом представлении графа вершины представлены прямоугольниками, а рёбра (связи) представлены горизонтальными и вертикальными линиями .
Поиск хорошего стягивающего дерева Любой планарный граф имеет вложение , такое, что содержит хорошее стягивающее дерево. Хорошее стягивающее дерево и подходящее вложение могут быть найдены для графа за линейное время. Не все вложения графа содержат хорошее стягивающее дерево.
См. также Остовное дерево Реализатор Шнайдера
Литература
Категория:Остовное дерево Категория:Планарные графы Категория:Вычислительные задачи теории графов