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:

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$:

Now draw all the edges that connect adjacent layers:

And finally, draw all the other edges:

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?

don'thave 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:11Consider 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