Another graph characteristic

Question

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?

Answer 1

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.

Answer 2

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.