Планаризация графа

Существует целый ряд методов укладки планарных графов на плоскости без пересечений изображений их ребер (или дуг), которые опираются на специальные упорядочения вершин, часто называемые каноническими. В этих алгоритмах сначала вершины упорядочиваются, а затем по одной (или группами) вершины последовательно добавляются в соответствии с найденной упорядоченностью к структуре данных, описывающей представление графа.

Некоторые планарные графы можно нарисовать на плоскости таким образом, чтобы каждая граница грани являлась выпуклым многоугольником. Такая выпуклая плоская укладка возможна для графа только тогда, когда границы всех граней являются простыми циклами. Таким образом, граф, не являющийся двусвязным, не имеет выпуклого представления, а для любого 3-связного графа существует выпуклое представление (пружинная теорема Татта).

К сожалению, на практике многие графы не являются планарными, более того, почти все графы не являются планарными. Согласно теореме Понтрягина — Куратовского граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных K₅ и K_3,3, где K₅ — полный 5-вершинный граф, а K_3,3 — полный двудольный граф, каждая доля которого состоит из 3 вершин. Можно пытаться непланарный граф сделать планарным, ибо удаляя из него как можно меньше ребер (эта проблема является NP-полной), либо удаляя те ребра чья вставка впоследствии может создать наименьшее число пересечений. Эта проблема минимизации пересечений является в общей постановке NP-трудной, но есть некоторые эвристики, которые позволяют получать вполне удовлетворительные результаты.

Можно рассматривать укладки графа не только на плоскости, но и на других поверхностях и в пространстве. В них вершины изображаются точками, а для изображения ребер используются жордановые кривые — непрерывные спряляемые линии, не имеющие пересечений. Изображенный таким образом некоторый граф в заданном пространстве, что кривые, соответствующие различным ребрам, пересекаются только в инцидентных этим ребрам вершинах, называется укладкой графа в это пространстве. Легко показать, что каждый граф укладывается в трехмерное пространство, а граф укладывается на сфере тогда и только тогда, когда он планарен.

Различные меры непланарности графов представляют такие их характеристики, как род  графа, число скрещиваний  графа, толщина  графа  и искаженность графа.

Многие алгоритмы рисования работают лишь с 2- и 3-связными графами. Поэтому, если мы хотим применить такой алгоритм, следует увеличить связность исходного графа путем добавления новых ребер. После получения изображения увеличенного графа добавленные ребра можно удалить. Поскольку при таком преобразовании желательно не слишком увеличивать граф, можно пытаться минимизировать количество добавляемых ребер. Однако проблема добавления минимального числа ребер к планарному графу так, чтобы результирующий граф был планарным и двусвязным, является NP-трудной. Вместе с тем вполне удовлетворительного результата можно добиться с помощью приближенного алгоритма.

Литература

• Касьянов В. Н., Евстигнеев В. А. Графы в программировании: обработка, визуализация и применение. – СПб.: БХВ-Петербург, 2003. – 1104 c.
• Касьянов В.Н., Касьянова Е.В. Визуализация информации на основе графовых моделей // Научная визуализация. – 2014. – Том. 6, N 1. – С. 31 – 50.
• Касьянов В.Н., Касьянова Е.В. Визуализация информации на основе графовых моделей. – Новосибирск: НГУ, 2014. – 149 с.