Параметризованные алгоритмы графического представления графов: различия между версиями

Задача односторонней минимизации пересечений (One-sided crossing minimization, OSCM) может рассматриваться как некоторая форма построения двудольного графа <math>G = (V_1, V_2, \; E)</math>, у которого все вершины из разбиения <math>V_i \;</math> присвоены к одной и той же линии (также называемой уровнем) <math>L_i \;</math> на плоскости, при этом линии <math>L_1 \;</math> и <math>L_2 \;</math> параллельны. Присваивание вершин к линии <math>L_1 \;</math> фиксировано; присваивание к линии <math>L_2 \;</math> свободно и выбирается таким образом, чтобы минимизировать количество пересечений между ребрами, представленными в виде отрезков прямых.