Например, вот такой граф:

картинка

Бесхордовых циклов тут три (идем вправо по одному из трех путей и возвращаемся обратно по любому из остальных, 6 вариантов делим на два, ибо обошли каждый цикл в двух направлениях). Если требовать, чтобы не было более короткого пути между двумя вершинами в цикле, то цикл только один — внешние ребра. Если же требовать, чтобы вообще лишних путей между вершинами не было, то циклов вообще нет. Но мне кажется, что вы хотите видеть тут 2 цикла — вокруг нижней и верхней замкнутой области, так?

Эта задача очень похожа на известную задачу выделения граней у планарного графа. С тем лишь дополнением, что надо удалить "петли" если цикл проходит по каким-то вершинам несколько раз. Ну, и компоненты связности внутри граней разрешены и игнорируются. В приведенном алгоритме они ничего не ломают — просто он в случае их наличия выдает не совсем грани графа, а просто замкнутые циклы, как вам и надо.

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

Единственное усложнение тут, что вы можете получить цикл с касаниями с каким-то произвольным сдвигом. Тогда просто удалять вершины между двумя повторениями одной вершины нельзя — вы можете удалить внешность цикла, оставив только внутренность. Но это лечится нахождением самой нижней-левой вершины в цикле. Если начинать обход цикла с нее, то уже можно спокойно удалять все вершины между двумя повторениями одной и той же вершины. Главное, чтобы эта самая нижняя-левая вершина оставалась в ответе.