При заданном неориентированном графе, каким будет алгоритм для нахождения всех многоугольников внутри такого графа? Вот пример графика с многоугольниками в цвете.

Обратите внимание, что существует многоугольник ABCIHGJKLMLKA, который включает в себя узлы KLM, но многоугольник CDEG не включает F.

Я читал о решениях этой проблемы, но без листового требования, которое у меня есть. Некоторые аксиомы, которые существуют в предыдущих решениях, состоят в том, что каждое ребро используется только дважды, однако тупиковые ребра должны быть пройдены в общей сложности четыре раза. То есть существует многоугольник, который содержит все внешние узлы ABCDEFGJKLMLKA, однако он отбрасывается так, как если бы он был обращен наружу.

Одно решение подобной проблемы, без листьев, описано здесь:http://blog.reactoweb.com/2012/04/algorithm-101-finding-all-polygons-in-an-undirected-graph/

ОБНОВИТЬ

Кажется, что связанное решение не работает, как задумано, пример этого иллюстрируется:

Алгоритм будет проходить по графику A-B-C-A-E-D-C, идентифицируя треугольник ABC, но также и многоугольник CAEDC, который не предназначен

UPDATE2

На самом деле существует простое решение этой проблемы: удалить большие полигоны, которые содержат точки других полигонов.