Гамма-алгоритм

Задача:

Определить, является ли граф планарным, и, если да, произвести его плоскую укладку.

Существует теорема Понтрягина-Куратовского, которая говорит, что граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных [math] K_{5} [/math] или [math] K_{3, 3} [/math]. Но этот критерий очень трудно проверить на практике, поэтому данная теорема представляет лишь теоретический интерес.

Чтобы проверить планарность графа и произвести его плоскую укладку, удобно пользоваться гамма-алгоритмом.

Входные данные

На вход алгоритму подаются графы со следующими свойствами:

1. Граф связный,
2. Граф содержит хотя бы один цикл,
3. Граф не имеет мостов.

Если нарушено свойство [math]1[/math], то граф нужно укладывать отдельно по компонентам связности. Если нарушено свойство [math]2[/math], то граф — дерево и нарисовать его плоскую укладку тривиально.

Более подробно рассмотрим случай, когда в графе [math]G[/math] нарушено свойство [math]3[/math]. Сначала все мосты нужно убрать, далее произвести отдельную укладку всех компонент следующим образом: уложим одну компоненту связности, а следующую компоненту, связанную с первой в графе [math]G[/math] мостом, будем рисовать в той грани, в которой лежит вершина, принадлежащая мосту. Иначе может сложиться ситуация, когда концевая вершина моста будет находиться внутри плоского графа, а следующая компонента - снаружи. Таким образом мы сможем соединить мостом нужные вершины. Далее будем так поступать с каждой новой компонентой.