Ответ 1
Это очень специфический экземпляр проблемы глобальной маршрутизации. Глобальная маршрутизация - хорошо изученная проблема в САПР СБИС (где нужно прокладывать миллионы сетей в интегральной схеме). Проблема NP-полная и может быть решена по-разному в зависимости от компромисса между временем выполнения и качеством. Следующая wiki - хорошая отправная точка:
http://en.wikipedia.org/wiki/Routing_(electronic_design_automation)
В данной статье приводится обзор различных методов:
http://dropzone.tamu.edu/~jhu/publications/HuIntegration01.pdf
Имейте в виду, что указатели, которые я дал, обычно пытаются решить гораздо более сложную версию проблемы, о которой вы говорили. Тем не менее, математические концепции остаются теми же.