Repulsive Curves
CHRIS YU, Carnegie Mellon University
HENRIK SCHUMACHER, RWTH Aachen University
KEENAN CRANE, Carnegie Mellon University
This paper proposes an interesting way of computing curves (edges) with repulsive forces. See Figure 26 which compares graphviz undirected graph layout with their proposed method. I wonder if this can be made fast enough to be useful. The study does not stress performance in terms of running time. But it is a promising direction for further work and suggests it might be possible to clean up global spline routing somehow.
This paper has most likely a nice approach for global edges untangling using the tangent-point energy.
I would not worry much about computation performance given these factors:
Acceleration is on the web (webGL, wasm)
It is possible to teak an algorithm parameters to reduce its complexity or runtime (resolution, semi global,…)
If an algo is unpractical for a 1000 elements graph, why not to take advantage of it for smaller graphs 10 ~ 100 elements ? Which would cover still a good portion of use cases.
We have to note that this paper goes in the direction of considering edges as first class citizen. I do not say that this should not be the case, but I think that this should depend on what the user wants depeding on his graph class. Sticking such an algo unconditionally to the layout of all graphs might be counter productive.
More about what I mean by Graph classes and vertices vs edges importance in this Throughs about Graph Theory readme
Cost based edges crossing avoidance, is I think not of completely different nature than energy based. I experimented that in this graphysics repo, but I only used straight lines edges model for that. There we can see that combining approaches is possible (collision based for nodes live interaction + cost based for initial layout)
When it comes to random path based cost map, I did actually implement that in another context : Sampling seeds avoiding a path in this Voronoi web tool (see Shaped tesselation area section)
So as a conclusion, if this algo is worth it ? IMHO, yes absolutely.
I would add to that, what matters is not only the algo, but its integration type, is it going to be a single shot, or iterative, can it come on top of a user interactive live graph or not, as I consider graph interactivity (mutations, filtering and explorations) as main elements on providing a simpler, nicer looking graph for multiple use cases.
As our tradition, we can always make the algorithm used an option. Going in the opposite direction as to performance, we’ve always wanted to try the edge layout in dot that only uses 4 points, especially as spline routing for larger graphs can be prohibitively expensive.
I’m one of the authors of the paper mentioned above (and a long-time fan of GraphViz). Though we took a very cursory look at graph layout, it seems there are some fun and interesting possibilities (beyond the simple example in the paper) and we’d be glad to discuss more. We also have some code that is reasonably straightforward to use. Feel free to reach out at kmcrane@cs.cmu.edu