Как найти оптимальный путь для каждой пары элементов так, чтобы пути соединительных линий не пересекались?
задача в вашей формулировке не имеет решений, кроме вырожденных (когда всё сразу совпадает один к одному).
во-первых, если надо соединять все N элементов, то тупиковых ситуаций с красными линиями никак не избежать, просто потому, что для того, чтобы поменять местами пару линий  вам нужно иметь хотя бы одну свободную полосу.
во-вторых, у вас написано: "квадрат", а при одной свободной полосе, в части случаев его не будет хватать по длине.  для того, чтобы поменять местами две линии, надо три ячейки в длину: из первой на свободную временную, со второй на первую, и со временной на вторую.  так что, в худшем случае (множество линий, которые надо менять местами попарно), это не квадрат, а прямоугольник с соотношением сторон примерно два к трём.
Мне кажется, что вот эта статья может вам помочь (проверка графа на планарность): https://ru.m.wikipedia.org/wiki/%D0%9F%D1%80%D0%BE...
Пересечением в вашем случае является совпадение переходов из вершины A в вершину B.