ГлавнаяПри визуализации графов, когда рёбра графа представляются ломаными (последовательностью отрезков, соединённых в точках излома), желательно минимизировать число изломов на ребро (что иногда называется сложностью кривой) или общее число изломов на рисунке. Минимизация изломов — это алгоритмическая задача поиска рисунка графа, минимизирующего указанные величины.
Исключение изломов
Классическим примером минимизации изломов служит теорема Фари, утверждающая, что любой планарный граф можно нарисовать без изломов, то есть можно найти планарное вложение графа, в котором все рёбра будут представлены отрезками.
Представление графа, в котором рёбра не имеют изломов и параллельны осям, иногда называется прямоугольным представлением и является одним из вариантов представления с ортогональным пересечением рёбер, в котором все пересечения рёбер происходят под прямым углом. Однако определение, имеет ли планарный граф прямоугольное преставление, является NP-полной задачей. NP-полной задачей является также определение, имеет ли произвольный граф прямоугольное представление при допущении пересечений рёбер.
Минимизация изломов
Тамассиа показал, что минимизация изломов ортогонального рисунка планарных графов, в котором вершины размещаются в узлах целочисленной решётки а рёбра рисуются в виде ломаных, состоящих из отрезков, параллельных осям, может быть осуществлена за полиномиальное время путём перевода задачи в задачу поиска потока минимальной стоимости. Однако если изменить способ вложения планарного графа, задача минимизации изломов становится NP-полной и должна решаться методами, такими как целочисленное программирование, которое не гарантирует одновременность получения точного решения и быстрой скорости работы.
Несколько изломов на ребро
Многие стили рисования графов позволяют изломы, но в ограниченном виде — сложность кривой этих представлений (максимальное число изломов на одно ребро) ограничивается некоторой константой. Разрешение этой константе подрасти может быть использовано для улучшения других характеристик рисунка, таких как площадь. В некоторых случаях стиль может оказаться возможным только при разрешении изломов. Например, не всякий граф имеет представление с ортогональным пересечением рёбер без изломов, или со сложностью кривой два, но любой граф имеет такой рисунок со сложностью кривой три.