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.