Универсальное препятствие в задаче продолжения вложения графа

В докладе будет разобран один из результатов Бояна Мохара. Рассматривается задача продолжения клеточного вложения подграфа до вложения всего графа в ту же поверхность. Оказывается, что в дополнении к вложенному подграфу можно выделить препятствие (некоторый подграф), имеющее ограниченную сложность, вложимость которого равносильна вложимости всего графа. Имеется алгоритм построения данного препятствия, линейный по числу ребер.