Welcome to Software Development on Codidact!
Will you help us build our independent community of developers helping developers? We're small and trying to grow. We welcome questions about all aspects of software development, from design to code to QA and more. Got questions? Got answers? Got code you'd like someone to review? Please join us.
Post History
This looks like it's a slightly restricted version of the circular dilation minimization problem in the theory of graph drawing. See, for example, https://doi.org/10.1080/00207168808803629. Specif...
Answer
#3: Post edited
by
r~~
·
2020-12-08T22:55:31Z (almost 4 years ago)
This looks like it's a slightly restricted version of the _circular dilation minimization problem_ in the theory of graph drawing. See, for example, https://doi.org/10.1080/00207168808803629.- Specifically, your problem can be expressed as finding a vertex numbering with minimal circular dilation for the graph formed from a vertex for each of your items and an undirected edge for every adjacent pair in your item use order (there can be multiple edges between two vertices, as in the case of B and D in your example).
I'm not familiar with a good heuristic for solving this problem, but I think circular graph layout engines sometimes use physical simulations to cut the NP knot. You might try that if researching the literature doesn't come up with anything useful.
- This looks like it's a slightly restricted version of the _circular dilation minimization problem_ in the theory of [graph drawing](https://en.wikipedia.org/wiki/Graph_drawing). See, for example, https://doi.org/10.1080/00207168808803629.
- Specifically, your problem can be expressed as finding a vertex numbering with minimal circular dilation for the graph formed from a vertex for each of your items and an undirected edge for every adjacent pair in your item use order (there can be multiple edges between two vertices, as in the case of B and D in your example).
- I'm not familiar with a good heuristic for solving this problem, but I think circular graph layout engines sometimes use force-based physical simulations to cut the NP knot. You might try that if researching the literature doesn't come up with anything useful.
#2: Post edited
by
r~~
·
2020-12-08T22:54:18Z (almost 4 years ago)
This looks like it's a slightly restricted version of the _circular dilation minimization problem_ in the theory of graph layouts. See, for example, https://doi.org/10.1080/00207168808803629.- Specifically, your problem can be expressed as finding a vertex numbering with minimal circular dilation for the graph formed from a vertex for each of your items and an undirected edge for every adjacent pair in your item use order (there can be multiple edges between two vertices, as in the case of B and D in your example).
- I'm not familiar with a good heuristic for solving this problem, but I think circular graph layout engines sometimes use physical simulations to cut the NP knot. You might try that if researching the literature doesn't come up with anything useful.
- This looks like it's a slightly restricted version of the _circular dilation minimization problem_ in the theory of graph drawing. See, for example, https://doi.org/10.1080/00207168808803629.
- Specifically, your problem can be expressed as finding a vertex numbering with minimal circular dilation for the graph formed from a vertex for each of your items and an undirected edge for every adjacent pair in your item use order (there can be multiple edges between two vertices, as in the case of B and D in your example).
- I'm not familiar with a good heuristic for solving this problem, but I think circular graph layout engines sometimes use physical simulations to cut the NP knot. You might try that if researching the literature doesn't come up with anything useful.
#1: Initial revision
by
r~~
·
2020-12-08T22:53:35Z (almost 4 years ago)
This looks like it's a slightly restricted version of the _circular dilation minimization problem_ in the theory of graph layouts. See, for example, https://doi.org/10.1080/00207168808803629. Specifically, your problem can be expressed as finding a vertex numbering with minimal circular dilation for the graph formed from a vertex for each of your items and an undirected edge for every adjacent pair in your item use order (there can be multiple edges between two vertices, as in the case of B and D in your example). I'm not familiar with a good heuristic for solving this problem, but I think circular graph layout engines sometimes use physical simulations to cut the NP knot. You might try that if researching the literature doesn't come up with anything useful.