577
правок
Изменения
→Описание алгоритма
Таким образом, мы получили плоскую укладку исходного графа <tex>G</tex>.
Опишем алгоритм коротко и формально:
# Инициализация. Выбирается простой цикл в исходном графе и изображается на плоскости.
# Общий шаг. Этот шаг повторяется до тех пор, пока граф не будет уложен или пока не будет получено, что граф не планарен.
#* строится множество сегментов
#* для каждого сегмента вычисляется величина <tex>|\Gamma(S)|</tex>. Если существует <tex>i</tex>: <tex>|\Gamma(S_{i})| = 0</tex>, то граф не планарен, алгоритм завершает работу
#* выбирается сегмент с минимальным числом <tex>|\Gamma(S_{i})|</tex>
#* в этом сегменте выбирается цепь между двумя контактными вершинами
#* эта цепь укладывается в любую грань, вмещающую данный сегмент
# Либо получена плоская укладка графа, либо граф оказался не планарен.
