5
$\begingroup$

This question concerns a method of drawing graphs and a graph characteristic about which I want to learn more.

Consider a connected directed graph with at least one node with in-degree 0 and one node with out-degree 0 (let's call it input-output-graph). Draw the input nodes equally spaced on layer 0:

enter image description here

Each node has a well-defined minimal distance $d_{in}$ to the input layer 0. Draw the nodes with $d_{in}=n$ on layer $n$:

enter image description here

Now draw all the edges that connect adjacent layers:

enter image description here

And finally, draw all the other edges:

enter image description here

Note, that none of these layers can be interpreted as the output layer, but based on a prescribed output layer the same construction can be made (in the opposite direction).

Each edge $(v_0,v_1)$ has a unique and well-defined length $\lambda$ with respect to the layers it connects. Let $v_0$ be a node on layer $n_0$ and $v_1$ a node on layer $n_1$.

$$\lambda((v_0,v_1)) = n_1 - n_0$$

Note, that by construction there cannot be an edge with $\lambda(e)>1$

The characteristic I have in mind is nothing but the distribution $d$ of the lengths $\lambda$:

$$d(l) = \text{number of edges $e$ with $\lambda(e)=l$}$$

Note, that the corresponding distribution with respect to the output layer may look quite different.

It is obvious that for strictly layered input-output-graphs (esp. trees) $d(1) = \text{number of edges}$ and $d(l)=0$ für $l\neq 1$.

But what about small-world or random input-output-graphs? Would the characteristic be a good one to distinguish them?

Question: Has this characteristic been defined before, and under which name?

$\endgroup$
  • 2
    $\begingroup$ It is a little strange that by your definition, all edges have length in $\{1,0,-1,-2,-3,\ldots\}$, the term "length" suggests something positive or at least non-negative. $\endgroup$ – Dirk Jun 29 '17 at 10:28
  • 2
    $\begingroup$ "negative length" means "directed backward". Is that ok? $\endgroup$ – Hans-Peter Stricker Jun 29 '17 at 10:50
  • 2
    $\begingroup$ I don't understand why it's important in your construction that there be any nodes with out-degree zero. $\endgroup$ – Sam Hopkins Jan 9 '18 at 6:38
  • 1
    $\begingroup$ There don't have to be! But only if there are the same construction can be made starting with an output layer. (If there were no nodes with in-degree zero, the construction could not be made at all.) $\endgroup$ – Hans-Peter Stricker Jan 9 '18 at 9:11
  • 2
    $\begingroup$ I was confused as well as you start with Consider a connected directed graph with at least one node with in-degree 0 and one node with out-degree 0 $\endgroup$ – Arnaud Mortier Jan 9 '18 at 20:18
2
+200
$\begingroup$

I don't know that your characteristic has been explicitly studied before, nor would I be surprised if it has, but it fits into a more general setting as follows.

The directed graph distance $d(a,b)$ from vertex $a$ to $b$ is the minimum length of a directed path from $a$ to $b$. (Of course, $d(a,b)\ne d(b,a)$ in general.)

Then the distance from a vertex to a set of vertices is also often defined, but in the directed case there are two versions: $$d(a,B)=\min\{d(a,b):b\in B\},$$ $$d(B,a)=\min\{d(b,a):b\in B\},$$ where again typically $d(a,B)\ne d(B,a)$.

You're looking at the case where $B$ is the set of all sources or the set of all sinks.

And then, upon picking an edge $e=(v_0,v_1)$, the random variable $$X(e)=d(v_0,B)-d(v_1,B)$$ tells you how much closer to $B$ you got.

$\endgroup$
2
$\begingroup$

This seems to be related to crossing numbers. Crossing numbers are minima over all possible drawings of the graph with certain restrictions; the least restricted version is where the only condition on arc images is that an arc image does not cross any 3rd vertex, and two arcs intersect transversally (if at all). One talks about rectilinear crossing number if each arc image must be a line segment. Book crossing number for a $k$-page book arises where one places all the vertices on a "book spine" (a straight line $B$) and each arc is drawn on one of the $k$ "pages" (i.e. half-planes attached to $B$). There are probably many more variations of this.

$\endgroup$
  • 1
    $\begingroup$ Do you mean that crossing number and the OP's distribution are correlated? $\endgroup$ – Bjørn Kjos-Hanssen Jan 16 '18 at 0:08
  • $\begingroup$ my gut feeling is that they should be somehow correlated. $\endgroup$ – Dima Pasechnik Jan 16 '18 at 17:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.