3 ms·

Hrm. Can any DAG be drawn as a box diagram?

Jtsummers 6y ago
The key part is performing a topological sort, which you can do on any DAG.
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 ago
  Isn'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 ago
    Hmm. 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 ago
  Hey 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
tunesmith 6y ago
I guess the answer is no... assuming 1 is on the bottom: 1->2; 1->4; 2->3; 3->4 Unless 4 is slanted.
hardmath123 6y ago
This is a great question! I don’t actually know the precise condition for box-diagram-ability of a DAG, but I’ve spent a long time thinking about it; it’s partly why I wrote that program. It’s not a deterministic algorithm, it’s powered by a SAT solver which may return “UNSAT” indicating failure. If anyone has a better answer I would be _very_ interested in reading about it!

The key part is performing a topological sort, which you can do on any DAG.

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 ago
Isn'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 ago
  Hmm. 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 ago
Hey 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

tunesmith 6y ago

I guess the answer is no... assuming 1 is on the bottom: 1->2; 1->4; 2->3; 3->4 Unless 4 is slanted.

hardmath123 6y ago

This is a great question! I don’t actually know the precise condition for box-diagram-ability of a DAG, but I’ve spent a long time thinking about it; it’s partly why I wrote that program. It’s not a deterministic algorithm, it’s powered by a SAT solver which may return “UNSAT” indicating failure. If anyone has a better answer I would be _very_ interested in reading about it!