worm2EtCetera, да, Вы немалые выкладки проделали.
Стыдно признаться, я выкладок вообще практически не проделывал. За бумажной энциклопедией поленился полезть, поэтому все формулки списаны из Wikipedia, и могут быть не точны.
Дальше дело идёт к неправильным многогранникам
Можно все-таки Архимедовы тела перед тем задействовать. Правда я никаких готовых формулок для них не нашел (впрочем, искал не слишком усердно), а выводить их самому, даже в простейших случаях типа кубооктаэдра - не слишком приятное занятие.
Надо заметить, что я не до конца уверен в правильности того, что мое решение хотя бы верное (до минимальности там далековато). Впрочем, контрпример (например, в случае тетраэдра) не придумывается.
путь по рёбрам многогранника не является оптимальным
Это да, практически наверняка есть более оптимальные пути. Выше обозначенные пути я привел лишь как самые простые примеры, удовлетворяющие (?) условиям задачи. Т.е. как аналог

для плоского случая.
P.S. Ваше рассуждение по поводу укорочения пути не понял. Не могли бы Вы снабдить его рисунком?