Четырехвалентные графы с крестовой структурой. Вложения в двумерные поверхности

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