Graph Theory Puzzle
Suppose I have an arbitrary graph realized physically as a web of strings. I anchor one vertex and pull outward on all loose leaf nodes till maximum tension. How do I compute all the taut/slack edges.
Is there an algorithm for this?
Conversation
Replying to
You could use many force directed algorithms with certain stiffness params and inspect the spring/gravity forces as you pull?
3
Replying to
Good question. Doable with finite elements in three-dimensions. Not sure about higher dimensions.
1
Replying to
I don’t think that problem is meaningful with graph theory, even with weighted edges.
1
2
Replying to
As a graph theory problem it smells ill-posed. Other have suggested simulation which should get the job done.
3
You’re unable to view this Tweet because this account owner limits who can view their Tweets. Learn more
Replying to
Graph theory is topological: relations matter but absolute distances (as projected in some visualization of a graph) are meaningless. The concepts of "taut/slack" assume some notion of "equilibrium length" from which tautness or slackness is measured: an absolute distance.
1





