Как построить граф по его граням?

Question

[RozeQz]

Нужно уложить планарный граф на плоскости, чтобы его ребра не пересекались. Один из способов это сделать - воспользоваться гамма-алгоритмом.
Получилось его реализовать программно, но на выходе алгоритма получаешь грани: внешнюю и внутренние.
Как, зная информацию о гранях графа, построить его плоскую укладку?


Стоит, наверное, начинать с построения внешней грани, а далее пытаться в правильном порядке разместить внутренние, но пока у меня нет представления, как это оптимально реализовать.

Спасибо.

Answer 1

[Wataru]

Как-то странно вы его релизовали. В самом алгоритме надо вершины и раскладывать на плоскости. Когда первый цикл укладываете - можно просто по большой окружности. Потом ребра или напрямую, если они внутри грани, или по дуге какой-то окружности вокруг.

Comments

[RozeQz]

Хорошо, я учту, что расставлять координаты вершинам можно внутри самого гамма-алгоритма. Но вопрос-то не об этом. Все-таки основной вопрос в том, как построить граф в соотстветствии с его гранями на плоскости.

Со времени публикации этого вопроса, я наткнулась на такую вещь как "вложение Татта" и пока что, кажется, что это мне может помочь.

[Wataru]

RozeQz, Просто по заданным граням - это очень сложная задача. Это надо делать по ним какой-нибудь рекурсивный перебор с возвратьм, чтобы пытаться понять, какая грань внутри какой. Фактически, вам придется весь гамма алгоритм повторить, только более запутанно и с перебором.