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

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

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

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

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