Is there a way to convert an undirect graph to an (x,y) coordinate system?

Question

For a project I am working on I have some txt files that have from id's, to id's, and weight. The id's are used to identify each vertex and the weight represents the distance between the vertices. The graph is undirected and completely connected and I am using c++ and openFrameworks. How can I translate this data into (x,y) coordinate points for a graph this 1920x1080, while maintaining the weight specified in the text files?

Answer 1

You can only do this if the dimension of the graph is 2 or less. You therefore need to determine the dimension of the graph--this is a measure of its connectivity. If the dimension is 2 or less, then you will always be able to plot the graph on a Euclidian plane while preserving relative edge lengths, as long as you allow the edges to intersect. If you prohibit intersecting edges, then you can only plot the graph on a Euclidian plane if the ratio of cycle size to density of cycles in the graph is sufficiently low throughout the graph (quite hard to compute). I can tell you how to plot the trickiest bit--cycles--and give you a general approach, but you actually have some freedom in how you plot this, so please, drop a comment or edit the question if you have a more specific request.

If you don't know whether you have cycles, then find out! Here are some efficient algorithms.

Plotting cycles. Give the first node in the cycle arbitrary coordinates. Give the second node in the cycle coordinates bounded by the distance from the first node. For example, if you plot the first node at (0,0) and the edge between the first and second nodes has length 1, then plot the second node at (1, 0). Now it gets tricky because you need to calculate angles.

Count up the number n of nodes in the cycle. In order for the cycle to form a polygon, the sum of the angles formed by the cycle must be (n - 2) * 180 degrees, where n is the number of sides (i.e., the number of nodes). Now you won't have a regular polygon unless all the edge lengths are the same, so you can't just use (n - 2) / n * 180 degrees as your angle. If you make the angles too sharp, then the edges will be forced to intersect; and if you make them too large, then you will not be able to close the polygon. Compute the internal angles as explained on StackExchange Math.

Repeat this process to plot every cycle in the graph, in arbitrary positions if needed. You can always translate the cycles later if needed.

Plotting everything else. My naive, undoubtedly inefficient approach is to traverse each node in each cycle and plot the adjacent nodes (the 'branches') layer by layer. Then rotate and translate entire cycles (including connected branches) to ensure every edge can reach both of its nodes. Finally, if possible, rotate branches (relative to their connected cycles) as needed to resolve intersecting edges.

Again, please modify the question or drop a comment if you are looking for something more specific. A full algorithm (or full code, in any common language) would make a very long answer.