Оба случая можно упростить, выкинув по две вершины. У
Yu_K 
- фактически одна сторона

, что верно и для

. У
svv склеиваются стороны

и

. То есть это сводится к четырехугольнику. А все способы склейки четырехугольника нам уже известны.
Более интересны случаи, когда никакие две подряд идущие стороны не склеиваются с другими двумя подряд идущими сторонами.
(Оффтоп)
Хотя лично я пришел к этой задаче совсем с другой стороны. Я пытался построить на плоскости один граф, и убедился, что это невозможно. Стал думать, на какой же поверхности его можно построить, и пришел к выводу, что на упомянутом в стартовом посте шестиугольнике он как раз помещается без самопересечений. То есть на торе.