3 ms·
If a box diagram has to be a planar graph, then no: digraph G { a -> {x y z} b -> {x y z} c -> {x y z} } cannot be drawn on th
by andreareina 6y ago
If a box diagram has to be a planar graph, then no:
digraph G {
a -> {x y z}
b -> {x y z}
c -> {x y z}
}
cannot be drawn on the plane without any crossings.
https://en.wikipedia.org/wiki/Three_utilities_problem https://en.wikipedia.org/wiki/Three_utilities_problem
- Tomminn 6y agoIsn't two "utilities" enough here? Suppose we have two components-- X and Y-- which depend on two other lower-level components-- A and B. How would you draw this as a block dependency diagram without repetition? If both X and Y depend on B, then X and Y must be above B, and both touch B. If X and Y are orthogonal rectangles, then the entire X-Y edge is obscured from below. This means that another lower-level component A must can only interact with either X or Y. You'd need to allow X or Y to no longer be orthogonal rectangles to overcome this, or need to give up on the vertical organization of dependencies.
- lopsidedBrain 6y agoHmm. You're right, not if we are restricting ourselves to rectangles. But if we make A u-shaped, with B nestled in it, we'll be in business!
- hoseja 6y agoHey there was a phys article about that problem today! https://phys.org/news/2020-08-solution-math-riddle.html https://phys.org/news/2020-08-solution-math-riddle.html