Генерация циклов ячеек карты простого планарного графа

Рассматривается конструктивный метод генерации циклов ячеек (chordless cycles) карты простого планарного графа. Циклы ячеек карты представляются как линейные комбинации циклов {DFS-базиса}. Искомые линейные комбинации строятся явно на основе выделенных свойств структуры вложенности циклов базиса и циклов ячеек карты графа. Карта планарного графа позволила отойти от общепринятого подхода генерации циклов и явно внести геометрию карты в структуру алгоритма. На множестве циклов базиса определяется отношение соседства, которое порождает корневые деревья структуры вложенности циклов. Ячейки карты графа являются результатом обхода данного множества корневых деревьев. Сложность предложенного алгоритма является кубической относительно числа вершин в графе. Рассматривается приложение алгоритма в рамках решения задач на планарном подразбиении.