Я пытаюсь написать алгоритм для получения граней неориентированного графа.Известно, что график, который я получаю на входе, является плоским и двусвязным.Однако список смежности графа не упорядочен ни в коем случае (по часовой стрелке или против часовой стрелки).
Я провел некоторое исследование по этому вопросу, и некоторые потоки StackOverflow предлагают сделать плоское вложение графа.Я нашел эту статью: Эффективное тестирование плоскостности , написанное Тарьяном и Хопкрофтом.В этой статье описывается алгоритм сложения ребер.
С другой стороны, я считаю код довольно трудоемким только для проверки плоскостности графа.Я не хочу рисовать график, мне все равно, есть ли много вложений, я просто хочу перечислить грани моего графика.Для этого мне нужен способ упорядочить края.Однако в статье не указывается порядок упорядочения по часовой стрелке как таковой, но в нем показан подпроцесс, задача которого состоит в упорядочении ребра (раздел 5, стр. 8), который, по-видимому, упорядочивается не по часовой стрелке, а по их значениям LOWPT..
Мой вопрос: есть ли какой-нибудь алгоритм для сортировки моего ребра, или мне нужно произвести плоское вложение графа, который, как я уже знаю, является плоским и двусвязным?
Спасибо