Тест на плоскостность слева направо

В теории графов , разделе математики , существует тест на лево-правую планарность. или критерий планарности де Фрессе-Розенштиля ^{[ 1 ]} — это характеристика плоских графов, основанная на свойствах деревьев поиска в глубину , опубликованная де Фрессейксом и Розенштилем ( 1982 , 1985 ). ^{[ 2 ]}^{[ 3 ]} и использовался ими вместе с Патрисом Оссона де Мендесом для разработки линейного времени тестирования планарности алгоритма . ^{[ 4 ]}^{[ 5 ]} В ходе экспериментального сравнения шести алгоритмов проверки планарности в 2003 году это был один из самых быстрых протестированных алгоритмов. ^{[ 6 ]}

Т-образные и Т-образные края

Для любого поиска в графа G ребра глубину встречающиеся при обнаружении вершины первом , определяют дерево поиска в глубину T of G . Это дерево Тремо , что означает, что каждое из оставшихся ребер ( кодерево ) соединяет пару вершин, которые связаны друг с другом как предок и потомок T. в Для определения двух отношений между парами ребер кодерева можно использовать три типа шаблонов, называемые T -подобными и T -противоположными отношениями.

На следующих рисунках узлы простого круга представляют вершины, узлы двойного круга представляют поддеревья, скрученные сегменты представляют пути дерева, а изогнутые дуги представляют ребра кодерева. Корень каждого дерева показан внизу рисунка. На первом рисунке ребра, обозначенные $\alpha$ и $\beta$ -подобны T , что означает, что в конечных точках, ближайших к корню дерева, они оба будут находиться на одной стороне дерева на каждом плоском рисунке. На следующих двух рисунках ребра с одинаковыми метками T -противоположны, что означает, что на каждом плоском рисунке они будут по разные стороны дерева.

Характеристика

Пусть G — граф, а — дерево Тремо графа G. T Граф G планарен тогда и только тогда, когда существует разделение ребер кодерева G на два класса так, что любые два ребра принадлежат одному классу, если они T -подобны, и любые два ребра принадлежат разным классам, если они T -противоположный.

Эта характеристика немедленно приводит к (неэффективному) тесту на планарность: определить для всех пар ребер, являются ли они T -подобными или T -противоположными, сформировать вспомогательный граф, имеющий вершину для каждого связную компоненту T - подобных ребер и ребро для каждой пары T -противоположных ребер и проверить, является ли этот вспомогательный граф двудольным . Для повышения эффективности этого алгоритма необходимо найти подмножество T -подобных и T -противоположных пар, достаточное для реализации этого метода без определения связи между всеми парами ребер во входном графе.

Ссылки

^ Ауэр, Кристофер; Гляйснер, Андреас; Ханауэр, Катрин; Веттер, Себастьян (2013), «Проверка планарности путем переключения поездов», Рисунок графика: 20-й Международный симпозиум, GD 2012, Редмонд, Вашингтон, США, 19–21 сентября 2012 г., Пересмотренные избранные статьи , Конспекты лекций по информатике, том. 7704, Берлин: Springer, стр. 557–558, doi : 10.1007/978-3-642-36763-2_51 .
^ де Фрессе, Х .; Розенштиль, П. (1982), «Характеристика планарности с поиском в глубину», Теория графов (Кембридж, 1981) , Анналы дискретной математики, том. 13, Северная Голландия, Амстердам-Нью-Йорк, стр. 75–80, MR 0671906 .
^ де Фрейссе, Х.; Розенштиль, П. (1985), «Характеристика плоских графов порядками Тремо», Combinatorica , 5 (2): 127–135, doi : 10.1007/BF02579375 , MR 0815578 , S2CID 35423242 .
^ де Фрессе, Юбер; Оссона де Мендес, Патрис ; Розенштиль, Пьер (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 .
^ Бойер, Джон М.; Кортезе, Пьер Франческо; Патриньяни, Маурицио; Ди Баттиста, Джузеппе (2004), «Хватит думать о своих P и Q: реализация быстрого и простого алгоритма тестирования планарности и внедрения на основе DFS», Рисование графика: 11-й Международный симпозиум, GD 2003, Перуджа, Италия, 21-24 сентября 2003 г. , Переработанные статьи , Конспекты лекций по информатике, том. 2912, Берлин: Springer, стр. 25–36, номер документа : 10.1007/978-3-540-24595-7_3 , MR 2177580 .

Дальнейшее чтение

Кайзер, Дэниел (2009), Реализация и анимация теста планарности слева направо , бакалаврская диссертация (на немецком языке), Констанцский университет , факультет компьютерных наук и информатики

[1] Ауэр, Кристофер; Гляйснер, Андреас; Ханауэр, Катрин; Веттер, Себастьян (2013), «Проверка планарности путем переключения поездов», Рисунок графика: 20-й Международный симпозиум, GD 2012, Редмонд, Вашингтон, США, 19–21 сентября 2012 г., Пересмотренные избранные статьи , Конспекты лекций по информатике, том. 7704, Берлин: Springer, стр. 557–558, doi : 10.1007/978-3-642-36763-2_51 .

[2] де Фрессе, Х .; Розенштиль, П. (1982), «Характеристика планарности с поиском в глубину», Теория графов (Кембридж, 1981) , Анналы дискретной математики, том. 13, Северная Голландия, Амстердам-Нью-Йорк, стр. 75–80, MR 0671906 .

[3] де Фрейссе, Х.; Розенштиль, П. (1985), «Характеристика плоских графов порядками Тремо», Combinatorica , 5 (2): 127–135, doi : 10.1007/BF02579375 , MR 0815578 , S2CID 35423242 .

[4] де Фрессе, Юбер; Оссона де Мендес, Патрис ; Розенштиль, Пьер (2006), «Деревья Тремо и планарность», Международный журнал основ компьютерных наук , 17 (5): 1017–1029, arXiv : math.CO/0610935 , doi : 10.1142/S0129054106004248 , MR 2270949 .

[5] де Фрессе, Юбер; Оссона де Мендес, Патрис (2012), «Деревья Тремо и планарность», Европейский журнал комбинаторики , 33 (3): 279–293, arXiv : math/0610935 , doi : 10.1016/j.ejc.2011.09.012 , MR 2864415 .

[6] Бойер, Джон М.; Кортезе, Пьер Франческо; Патриньяни, Маурицио; Ди Баттиста, Джузеппе (2004), «Хватит думать о своих P и Q: реализация быстрого и простого алгоритма тестирования планарности и внедрения на основе DFS», Рисование графика: 11-й Международный симпозиум, GD 2003, Перуджа, Италия, 21-24 сентября 2003 г. , Переработанные статьи , Конспекты лекций по информатике, том. 2912, Берлин: Springer, стр. 25–36, номер документа : 10.1007/978-3-540-24595-7_3 , MR 2177580 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]