in reply to Re^2: Visualizing a dependency graph in a web page
in thread Visualizing a dependency graph in a web page

> 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.

Replies are listed 'Best First'.
Re^4: Visualizing a dependency graph in a web page
by LanX (Saint) on Apr 01, 2022 at 21:46 UTC
    Yes, you are right. I remember discussing K5 and K3,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 Q3 °

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

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

[reply]
      Yup, we should be talking about upward planar drawings.

      Looking forward to finding out your final strategy for getting it onto a screen.

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

[reply]
        Thanks for the link, this helps.

        But I don't need it to be planar, that was introduced by the discussion.

        > Looking forward to finding out your final strategy for getting it onto a screen.

        I just realized again that my clients don't really know what they want, they've seen different pictures with boxes and arrows and agree to like it.

        Unfortunately different stakeholders have shown me diagrams with very different semantics and aim now.

        My fall back scenario is to turn a Gantt chart up-down and draw the boxes at the start of the bars.

        This would mean the source is on the top-left and the sink on the bottom-right

        Probably I can try and move lower boxes into empty left space to have it more top down.

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

[reply]

In Section Seekers of Perl Wisdom