Минимизация изломов

При визуализации графов, когда рёбра графа представляются ломаными (последовательностью отрезков, соединённых в точках излома), желательно минимизировать число изломов на ребро (что иногда называется сложностью кривой)^[1] или общее число изломов на рисунке^[2]. Минимизация изломов — это алгоритмическая задача поиска рисунка графа, минимизирующего указанные величины^[3][4].

Исключение изломов

Классическим примером минимизации изломов служит теорема Фари, утверждающая, что любой планарный граф можно нарисовать без изломов, то есть можно найти планарное вложение графа, в котором все рёбра будут представлены отрезками^[5].

Представление графа, в котором рёбра не имеют изломов и параллельны осям, иногда называется прямоугольным представлением и является одним из вариантов представления с ортогональным пересечением рёбер^[англ.], в котором все пересечения рёбер происходят под прямым углом^[6]. Однако определение, имеет ли планарный граф прямоугольное преставление, является NP-полной задачей^[7]. NP-полной задачей является также определение, имеет ли произвольный граф прямоугольное представление при допущении пересечений рёбер^[6].

Минимизация изломов

Тамассиа показал, что минимизация изломов ортогонального рисунка планарных графов, в котором вершины размещаются в узлах целочисленной решётки а рёбра рисуются в виде ломаных, состоящих из отрезков, параллельных осям, может быть осуществлена за полиномиальное время путём перевода задачи в задачу поиска потока минимальной стоимости^[8][9]. Однако если изменить способ вложения планарного графа, задача минимизации изломов становится NP-полной и должна решаться методами, такими как целочисленное программирование, которое не гарантирует одновременность получения точного решения и быстрой скорости работы^[10].

Несколько изломов на ребро

Многие стили рисования графов позволяют изломы, но в ограниченном виде — сложность кривой этих представлений (максимальное число изломов на одно ребро) ограничивается некоторой константой. Разрешение этой константе подрасти может быть использовано для улучшения других характеристик рисунка, таких как площадь^[1]. В некоторых случаях стиль может оказаться возможным только при разрешении изломов. Например, не всякий граф имеет представление с ортогональным пересечением рёбер^[англ.] без изломов, или со сложностью кривой два, но любой граф имеет такой рисунок со сложностью кривой три^[11].