- #1

- 221

- 0

Firstly, let me excuse myself for not knowing the most appropriate location to post this question. This is a question pertaining to Graph Theory, but the heart of the application is intended to be driven by the math and/or simulation of classical physics.

At work I am currently attempting to visualize a very large graph. The graph is initially too squished together and is altogether incomprehensible when drawn on screen. My plan is to simulate a physical scenario involving the graph, in which the end result of the system should yield a more "eye-pleasing" arrangement of vertices (nodes or points) and edges (a link between two nodes). The details are as follows:

I have a very specific graph that, due to its size, requires visualization of overall

The graph is special because I've arranged it in the following way:

There are approximately 500,000 vertices. Every vertex already has a desired y-coordinate that should not change. There are around 500 "rows" (one for each y-coordinate), and each row contains anywhere between 1 and 100,000 nodes. Edges can

Every vertex also has a desired colour/shape. The

I need a way to determine the x-coordinate of each and every node, such that vertices on the same row do not crowd each other, and the geometrical/physical length of each edge is minimized. Clearly, some more precise objective function will be necessary, but this description should suffice for the planning stages. In the end, plotting the (x,y,colour) of each node (and potentially joining some of the more major nodes with a transparent edge) should give a visual representation of how the graph is structured.

My plan is to motivate the algorithm by the physics required to simulate an interaction between "balls" joined by elastic "strings". Balls will gravitationally repel all other balls on the same row, and strings will have tension and elastic energy that try to bring the two ends closer together (and could potentially break if need be).

The physics would be simulated in an iterative fashion, where the system begins with some amount of potential energy, and each step of the simulation assigns new x-coordinates to each ball, based on the x-

Any suggestions or pointers as to the kind of equations or algorithms that could be used here? Thank you very much!

At work I am currently attempting to visualize a very large graph. The graph is initially too squished together and is altogether incomprehensible when drawn on screen. My plan is to simulate a physical scenario involving the graph, in which the end result of the system should yield a more "eye-pleasing" arrangement of vertices (nodes or points) and edges (a link between two nodes). The details are as follows:

I have a very specific graph that, due to its size, requires visualization of overall

*structure*. I cannot use any out-of-the-box graph visualization tools because the graph is simply too big, the goal is to get an idea of how the general layout looks, and I want to have fine-grain control over aspects such as the colour and the y-coordinates. This is going to fit into one image (maybe 5,000x5,000) so there won't even be enough room to have nodes larger than a few pixels. Point being: I doubt any free applications out there can satisfy my needs.The graph is special because I've arranged it in the following way:

There are approximately 500,000 vertices. Every vertex already has a desired y-coordinate that should not change. There are around 500 "rows" (one for each y-coordinate), and each row contains anywhere between 1 and 100,000 nodes. Edges can

__only exist between vertices on different rows__(edges will never join vertices on the same row). Finally, the graph is*sparse*with only around 5,000,000 edges.Every vertex also has a desired colour/shape. The

__x-coordinates are currently unknown__.I need a way to determine the x-coordinate of each and every node, such that vertices on the same row do not crowd each other, and the geometrical/physical length of each edge is minimized. Clearly, some more precise objective function will be necessary, but this description should suffice for the planning stages. In the end, plotting the (x,y,colour) of each node (and potentially joining some of the more major nodes with a transparent edge) should give a visual representation of how the graph is structured.

My plan is to motivate the algorithm by the physics required to simulate an interaction between "balls" joined by elastic "strings". Balls will gravitationally repel all other balls on the same row, and strings will have tension and elastic energy that try to bring the two ends closer together (and could potentially break if need be).

The physics would be simulated in an iterative fashion, where the system begins with some amount of potential energy, and each step of the simulation assigns new x-coordinates to each ball, based on the x-

*components*of all surrounding forces, to put the system into a more "stable" condition. The iterations would continue until the changes become minimal, converge, or after a fixed amount of time.Any suggestions or pointers as to the kind of equations or algorithms that could be used here? Thank you very much!

Last edited: