Граф задается матричным способом.
Как можно построить граф по этой матрице чтоб было минимально число пересечения ребер.

В общем виде нетривиальная задача...

Навскидку предлагаю эвристику: расположить вершины равномерно по окружности в таком порядке, чтобы количество пересечений рёбер было минимальным.