Двумерность: различия между версиями

Параметр является ''g(r)-двумерным'' (или просто ''двумерным''), если он равен не менее чем g(r) в графе-решетке размером <math>r \times r \;</math> и если он не повышается при взятии миноров (''g(r)-минорно-двумерный'') либо выполнении сжатий (''g(r)-сжато-двумерный''). Точное определение «графа-решетки» зависит от класса допустимых графов и от того, рассматривается ли минорная двумерность или двумерность со сжатием. Для случая минорной двумерности и для любого класса графов, свободного от H-миноров, «графом-решеткой» является решетка <math>r \times r \;</math>, т.е. планарный граф с <math>r^2 \;</math> вершин, расположенных в виде квадратной решетки, ребра которой связывают горизонтально и вертикально смежные вершины. В случае двумерности со сжатием «граф-решетка» определяется следующим образом:

1. Для планарных графов и графов, свободных от миноров с однократным пересечением, «граф-решетка» представляет собой решетку <math>r \times r \;</math>, частично [[триангуляция графа|триангулированную]] дополнительными ребрами, сохраняющими планарность.