Развёртка графа — функция , заданная над вершинами ориентированного графа и удовлетворяющая ряду условий.

Определение. Функция ${\displaystyle \phi (V)}$ называется обобщённой ( строгой ) развёрткой ориентированного графа ${\displaystyle G=(V,E)}$ , если ${\displaystyle \forall e\in E}$ , идущей от ${\displaystyle v_{1}}$ к ${\displaystyle v_{2}}$ выполняется неравенство ${\displaystyle \phi (v_{1})\leq \phi (v_{2})(\phi (v_{1})<\phi (v_{2}))}$ .

Интересным свойством строгой развёртки является то, что она задаёт собой ярусно-параллельную форму графа , причём ярусами в такой ЯПФ являются поверхности уровня развёртки.

Известно, что у любого фрагмента алгоритма существует по крайней мере одна кусочно-линейная обобщённая развертка .

Строгие и обобщённые развёртки графа алгоритма используются для эффективного распараллеливания алгоритма по методике В. В. Воеводина .