Timeline for How can I fit a tree graph into a grid?
Current License: CC BY-SA 4.0
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 30, 2023 at 17:15 | answer | added | Bogdan | timeline score: -2 | |
| May 17, 2022 at 14:32 | comment | added | Pikalek | The most promising thing I've found so far is something on the Biedl & Kant orthogonal drawing algorithm. It's long & I haven't had time to see if it can be distilled into an answer. | |
| May 10, 2022 at 11:21 | comment | added | Nakilon | With the goal of minimizing the number of dummy nodes it sounds rather like a hard (not even fully unsolvable?) programming contest problem than anything that you would an existing solver for in the wild. | |
| May 9, 2022 at 19:21 | history | edited | IanLarson | CC BY-SA 4.0 | added 20 characters in body |
| May 9, 2022 at 19:21 | comment | added | IanLarson | @Pikalek Reachability is more important than adjacency, yes. Splitting of nodes would be totally acceptable. | |
| May 9, 2022 at 19:16 | comment | added | IanLarson | @Mangata You are correct about the "fake" node. I've clarified the post. | |
| May 9, 2022 at 19:09 | history | edited | IanLarson | CC BY-SA 4.0 | Clarification. |
| May 9, 2022 at 14:38 | comment | added | Pikalek | For good answers here on GDSE, it would help if you edited to add details about the game design context for the problem so we could better understand which constraints are hard & which are flexible. I see several possible options in my graph drawing text, but without more info, I don't know which to recommend. | |
| May 9, 2022 at 14:33 | comment | added | Pikalek | For general trees on a square grid the answer is no, as any tree with more than 4 edges to a node will not map. However, I think it works with modifications. First, you need to 'split' nodes w/ too many edges. For instance, say you have node A with edges to B,C,D,E,F. A could be split A1 & A2 such that A1 connects to A2,B,C,D and A1 connects to A1,E,F. Reachability is the same & distance is preserved provided that edges between split nodes have a distance of 1. And as sort of mention, you either need to allow for dummy nodes or you need to allow edges to span across more than one cell. | |
| May 9, 2022 at 12:00 | history | tweeted | twitter.com/StackGameDev/status/1523633895203393539 | ||
| May 9, 2022 at 11:32 | comment | added | Mangata | I mean, This problem arises if there are similar restrictions like parent and child nodes must be adjacent in the grids. Maybe i'm wrong because I noticed that there is a ‘fake’ node in the example graph of the post. | |
| May 9, 2022 at 11:03 | comment | added | DMGregory♦ | Mangata: I think it's safe to presume in this context that the grid is either unbounded/grows appropriately as we place nodes, or that the first step of our algorithm pre-sizes the grid large enough to fit the tree with at least high probability, even if that means making the grid dimensions disproportionately large compared to the tree depth. | |
| May 9, 2022 at 4:43 | comment | added | Mangata | Concise answer: No, you can't, unless many nodes in the tree graph have only one branch or less. The space required for tree graph grows exponentially. But the space grows geometrically in grid. It's like (n^k) vs k^2. | |
| May 9, 2022 at 3:24 | comment | added | BlueRaja - Danny Pflughoeft | This is an interesting question that I haven't seen before. You'll probably get better answers on cs.stackexchange.com or even cstheory.stackexchange.com | |
| May 9, 2022 at 3:12 | history | edited | IanLarson | CC BY-SA 4.0 | Swapped out image. |
| May 9, 2022 at 2:59 | history | edited | IanLarson | CC BY-SA 4.0 | Added image. |
| May 9, 2022 at 2:30 | history | asked | IanLarson | CC BY-SA 4.0 |