Проблема планарности графов

Напомним, что абстрактный граф называется плоским (или планарным), если он может быть реализован в виде плоского геометрического графа, т. е. изображен на плоскости в виде графа, ребра которого пересекаются только в вершинах. Как отмечалось в пункте 1.6, далеко не всякий (даже конечный) граф обладает указанным свойством. Для большинства графов плоскость является слишком «тесной», и для их реализации необходимо трехмерное пространство (см. теорему 2). Так, немыслимо реализовать на плоскости граф, моделирующий потоки в нервной системе человека, ведь мозг состоит из огромного числа нервных клеток, связи между которыми осуществляются через многочисленные непересекающиеся нервные волокна. Философы видят в этом факте объяснение того, почему разумная материя может существовать только в трехмерном пространстве. Для заданного абстрактного графа не так-то просто решить проблему планарности, т. е. ответить на вопрос — является ли он плоским. Подобные проблемы часто возникают в приложениях. Так, например, при проектировании транспортных магистралей важно избавиться от нежелательных пересечений или свести количество таких пересечений к минимуму. При создании печатных плат пересечение проводников приводит к замыканию в электрической цепи и, следовательно, недопустимо. Логические схемы, представленные графами, более наглядны и информативны, если их ребра не имеют излишних пересечений. При решении подобного круга задач сначала, как правило, рисуется граф, имеющий «неправильное» изображение. Затем анализируются свойства этого графа и вычисляется минимально возможное количество нежелательных пересечений (в случае плоского графа их количество равно нулю). Лишь после этого осуществляется «правильное» изображение графа. В этом параграфе мы рассмотрим ряд свойств плоских графов и рассмотрим задачи, примыкающие к проблеме планарности абстрактных графов.