Return to 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?

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?

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:

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

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?

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?