В теории графов , разделе математики , тест на лево-правую планарность или критерий планарности де Фрейссейкса–Розенштиля [1] представляет собой характеристику планарных графов, основанную на свойствах деревьев поиска в глубину , опубликованную де Фрейссейксом и Розенштилем (1982, 1985) [2] [3] и использованную ими совместно с Патрисом Оссоной де Мендесом для разработки линейного алгоритма проверки планарности по времени . [4] [5] В экспериментальном сравнении шести алгоритмов проверки планарности, проведенном в 2003 году, этот алгоритм оказался одним из самых быстрых из протестированных. [6]
Для любого поиска в глубину графа G рёбра , обнаруженные при первом обнаружении вершины , определяют дерево поиска в глубину T графа G . Это дерево Тремо , что означает, что каждое из оставшихся рёбер ( cotree ) соединяет пару вершин, которые связаны друг с другом как предок и потомок в T . Для определения двух отношений между парами ребер cotree , называемых отношениями T -подобия и T -противоположности , можно использовать три типа шаблонов .
На следующих рисунках простые круговые узлы представляют вершины, двойные круговые узлы представляют поддеревья, скрученные сегменты представляют пути дерева, а изогнутые дуги представляют ребра содерева. Корень каждого дерева показан в нижней части рисунка. На первом рисунке ребра, помеченные и , являются T -подобными, что означает, что в конечных точках, ближайших к корню дерева, они оба будут находиться на одной стороне дерева в каждом плоском рисунке. На следующих двух рисунках ребра с одинаковыми метками являются T -противоположными, что означает, что они будут находиться на разных сторонах дерева в каждом плоском рисунке.
Пусть G — граф, а T — дерево Тремо графа G. Граф G является планарным тогда и только тогда, когда существует разбиение ребер кодерева графа G на два класса, такое, что любые два ребра принадлежат одному и тому же классу, если они T -подобны, и любые два ребра принадлежат разным классам, если они T -противоположны.
Эта характеристика немедленно приводит к (неэффективному) тесту на планарность: определить для всех пар ребер, являются ли они T -подобными или T -противоположными, сформировать вспомогательный граф, который имеет вершину для каждого связного компонента T -подобных ребер и ребро для каждой пары T -противоположных ребер, и проверить, является ли этот вспомогательный граф двудольным . Чтобы сделать этот алгоритм эффективным, необходимо найти подмножество T -подобных и T -противоположных пар, достаточное для выполнения этого метода без определения отношения между всеми парами ребер во входном графе.
