Вы можете сделать это, только если размер графика 2 или меньше. Поэтому вам необходимо определить размер графика - это показатель его связности. Если размер равен 2 или меньше, то вы всегда сможете построить график на евклидовой плоскости с сохранением относительной длины ребер, если вы позволите ребрам пересекаться. Если вы запрещаете пересечение ребер, то вы можете построить график на евклидовой плоскости только в том случае, если отношение размера цикла к плотности циклов в графе достаточно низкое по всему графу (довольно сложно вычислить). Я могу рассказать вам, как построить самый сложный фрагмент - циклы - и дать вам общий подход, но на самом деле у вас есть некоторая свобода в том, как вы это строите, поэтому, пожалуйста, оставьте комментарий или отредактируйте вопрос, если у вас есть более конкретный c запрос.
Если не знаете, есть ли у вас циклы, то узнайте! Вот несколько эффективных алгоритмов .
Графические циклы. Дайте первому узлу цикла произвольные координаты. Задайте второй узел в координатах цикла, ограниченных расстоянием от первого узла. Например, если вы нанесете первый узел на (0,0), а край между первым и вторым узлами имеет длину 1, тогда нанесите второй узел на (1, 0). Теперь это становится сложным, потому что вам нужно вычислить углы.
Подсчитайте количество n узлов в цикле. Для того чтобы цикл сформировал многоугольник, сумма углов, образованных циклом, должна быть (n - 2) * 180 degrees, где n - количество сторон (т. Е. Количество узлов). Теперь у вас не будет правильного многоугольника, если длина всех ребер не будет одинаковой, поэтому вы не можете просто использовать (n - 2) / n * 180 degrees в качестве угла. Если вы сделаете углы слишком острыми, то края будут вынуждены пересекаться; и если вы сделаете их слишком большими, то вы не сможете закрыть многоугольник. Вычислите внутренние углы, как объяснено в StackExchange Math .
Повторите этот процесс, чтобы построить каждый цикл на графике, в произвольных положениях, если необходимо. Вы всегда можете преобразовать циклы позже, если это необходимо. ) слой за слоем. Затем вращайте и перемещайте целые циклы (включая соединенные ветви), чтобы каждое ребро могло достичь обоих своих узлов. Наконец, если возможно, поверните ветви (относительно их соединенных циклов) по мере необходимости, чтобы разрешить пересекающиеся края.
Опять же, измените вопрос или оставьте комментарий, если вы ищете что-то более конкретное c. Полный алгоритм (или полный код на любом распространенном языке) дал бы очень длинный ответ.