Дан граф. Надо его нарисовать на экране, так, чтобы он ещё нормально выглядел(граф задан либо матрицой смежности, либо списком ребер). Т.е. задача состоит в том, чтобы вычилить координаты вершин...

Попробуй его рисовать "по кругу".

acp:
Поясни, что значит "по кругу"

1. Прямоугольник, в котором должен быть нарисован граф известен, т.е. ширина/высота. Т.е. соответственно известен диаметр умещающегося в нём круга.
2. Центры твоих вершины должны равномерно располагаться по ободу этого круга. Т.е. предположим у тебя 10 вершин. Соответственно, центр каждой вершины должен лежать на ободе через каждые 360 / 10 = 36 градусов. Для этого смотрим параметрическое уравнение окружности

Код

x = R cos a y = R sin a

где a - твой угол, меняется с шагом 36. На этой основе и вычисляешь x, y для каждого центра вершины графа.

Понятно, но кажется что любой граф, который может поместиться на экране, это не нарисует в нормальном для восприятия человека виде

Разве сложно? Наоборот - оптимальный вариант IMHO. Может, ты не понял, что я имею в виду?