В теории графов , ветвь математики , то тест плоскостность слева направо или де Fraysseix-Rosenstiehl критерий плоскостности [1] является характеристика плоских графов на основе свойств поиска в глубину деревьев , опубликованных де Fraysseix и Rosenstiehl ( 1982 , 1985 ) [2] [3] и использовались ими вместе с Патрисом Оссона де Мендес для разработки алгоритма проверки линейной временной планарности . [4] [5]При экспериментальном сравнении шести алгоритмов проверки планарности в 2003 году это был один из самых быстрых алгоритмов. [6]
Т-образные и Т-противоположные края
Для любого поиска в глубину в виде графа G , то ребра , возникающие при обнаружении в вершину впервые определить глубину первого дерева поиска Т из G . Это дерево Trémaux , а это означает , что остальные ребра (The cotree ) каждый подключить пару вершин, которые связаны друг с другом в качестве предка и потомка в T . Для определения двух отношений между парами ребер cotree могут использоваться три типа шаблонов, которые называются отношениями T- подобным и T -противоположным .
На следующих рисунках узлы простого круга представляют вершины, узлы двойного круга представляют поддеревья, скрученные сегменты представляют собой пути дерева, а изогнутые дуги представляют ребра котлована. Корень каждого дерева показан внизу рисунка. На первом рисунке края обозначены а также являются T- подобными, что означает, что в конечных точках, ближайших к корню дерева, они оба будут на одной стороне дерева на каждом плоском чертеже. На следующих двух рисунках края с одинаковыми метками расположены Т- образно, что означает, что они будут на разных сторонах дерева на каждом плоском чертеже.
![]() а также похожи на Т | ![]() а также Т-противоположны | ![]() а также Т-противоположны |
Характеристика
Пусть G граф , и пусть T будет Trémaux дерево G . Граф G является плоским тогда и только тогда, когда существует разделение ребер cotree графа G на два класса, так что любые два ребра принадлежат одному классу, если они T- подобны, и любые два ребра принадлежат разным классам, если они T -противоположный.
Эта характеристика немедленно приводит к неэффективному () тесту планарности: определить для всех пар ребер , являются ли они T -alike или Т -opposite, образует вспомогательный граф , который имеет вершину для каждого подключенного компонента из T -alike ребер и ребра для каждой пары T -противоположных ребер и проверяем, является ли этот вспомогательный граф двудольным . Чтобы сделать этот алгоритм эффективным, необходимо найти подмножество пар Т- подобных и Т- противоположных пар, которых достаточно для выполнения этого метода без определения отношения между всеми парами ребер во входном графе.
Рекомендации
- ^ Ауэр, Кристофер; Глайсснер, Андреас; Ханауэр, Катрин; Веттер, Себастьян (2013), «Проверка планарности путем переключения поездов», Рисование графика: 20-й Международный симпозиум, GD 2012, Редмонд, Вашингтон, США, 19-21 сентября 2012 г., Пересмотренные избранные статьи , Лекционные заметки по компьютерным наукам, 7704 , Берлин: Springer, стр. 557–558, DOI : 10.1007 / 978-3-642-36763-2_51.
- ^ де Фрейссе, Х .; Rosenstiehl, P. (1982), "Характеристика планарности методом поиска в глубину", Graph Theory (Cambridge, 1981) , Annals of Discrete Mathematics, 13 , North-Holland, Amsterdam-New York, стр. 75–80, Руководство по ремонту 0671906.
- ^ de Fraysseix, H .; Rosenstiehl, P. (1985), "Характеристика плоских графов порядков Trémaux", Combinatorica , 5 (2): 127-135, DOI : 10.1007 / BF02579375 , MR 0815578.
- ^ де Фрейссе, Юбер; Оссона де Мендес, Патрис ; Розенштиль, Пьер (2006), «Деревья Тремо и планарность», Международный журнал основ компьютерных наук , 17 (5): 1017–1029, arXiv : math.CO/0610935 , doi : 10.1142 / S0129054106004248 , MR 2270949.
- ^ де Фрейссе, Юбер; Оссона де Мендес, Патрис (2012), «Деревья Тремо и планарность», Европейский журнал комбинаторики , 33 (3): 279–293, arXiv : math / 0610935 , doi : 10.1016 / j.ejc.2011.09.012 , MR 2864415.
- ^ Boyer, John M .; Кортезе, Пьер Франческо; Патриньяни, Маурицио; Ди Баттиста, Джузеппе (2004), «Перестаньте думать о ваших P и Q: реализация быстрого и простого алгоритма проверки планарности и внедрения на основе DFS», Graph Drawing: 11th International Symposium, GD 2003 Perugia, Italy, 21-24 сентября 2003 г. , пересмотренная документы , Lecture Notes в области компьютерных наук, 2912 , Берлин: Springer, С. 25-36,. DOI : 10.1007 / 978-3-540-24595-7_3 , MR 2177580.
дальнейшее чтение
- Кайзер, Даниэль (2009), Реализация и анимация тестов ссылок-Rechts-Planaritätstests , Bachelorarbeit (на немецком языке), Университет Констанца , FB Informatik und Informationswissenschaft