But I also need it to be ranked by phases, that's where the time-axis comes in.

• the jobs without dependency run in phase 0
• the jobs depending on phase 0 run in phase 1
• and so on

Anyway talking about it helped me sketching my own algorithm already... :)

I searched DAG with graphviz, but couldn't see them ranked in phases and the nodes were all circles (I have practically no hands-on experience with graph-viz)

> automate creating images of them without edges having to cross each other, etc.

Really? I have doubts it's always possible to draw a planar graph.

consider a 3d-cube, how do you want to draw a planar graph without crossings - here x ?

    0
  / | \
 /  |  \
A   B   C
|\ / \ /|
| x   x |
|/ \ / \|
a   b   c
 \  |  /
  \ | /
    1
[download]

> automate creating images of them without edges having to cross each other, etc.

Really? I have doubts it's always possible to draw a planar graph.

consider a 3d-cube, how do you want to draw a planar graph without crossings - here x ?

There are two basic cases where the graphs cannot be embedded in a 2-d representation without crossing lines:

1. 3 nodes that are each fully connected w/ 3 other nodes

   a -> A, B, C
   b -> A, B, C
   c -> A, B, C
   [download]

2. 5 densely connected nodes

   A -> B, C, D, E
   B -> C, D, E
   C -> D, E
   D -> E
   [download]

All graphs that can't be embedded in a 2-d plane have those cases embedded in them.

Your cube example actually can be embedded. You just lose the pretty perspective (or gain a new one...).

      0
    / | \
   /  |  \
  /   B   \
 /   / \   \
A---a   c---C
 \   \ /   /
  \   1   /
   \  |  /
    \ | /
      b
[download]

This is proven by Kuratowski's theorem and is discussed here.

---

#11929 First ask yourself `How would I do this without a computer?' Then have the computer do it the same way.

Yes, you are right. I remember discussing K₅ and K_3,3 in university

> Your cube example actually can be embedded. You just lose the pretty perspective (or gain a new one...).

And this a good example why a good question often matters more than a good answer.

In the context of this task I need the diagram to have a top-down semantic with Y being the time-axis.

So 0 and 1 must be at different extremes, so flattening won't be possible with Q₃ °

Cheers Rolf
_{(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery}

°) FWIW I remember the notation B₃, but all these pandemics in the meantime must have messed with my head :)

> > automate creating images of them without edges having to cross each other, etc.

> Really? I have doubts it's always possible to draw a planar graph.

You're quite right, that was a brainfart.