6. Calculating metrics of arrangements
As it might seem obvious to most readers, we can calculate values (or metrics) on these arrangements. These values depend on the graph drawn and on the arrangement of its vertices.
The length of an edge of a graph can be defined when its vertices are mapped to known positions. In a (linear) arrangement \pi of an n-vertex graph G=(V,E), where \pi(u) denotes the position 1 <= \pi(u) <= n, the length of an edge connecting vertices u and v can be defined as
d_{\pi}(u,v) = |\pi(u) - \pi(v)|
The sum of all edge lengths is, then
D_{\pi}(G) = \sum_{uv\in E(G)} d_{\pi}(u,v)
This value can be calculated by the ipelet and be displayed beneath the arrangement. This is done by checking the appropriate checkbox in the ipelet's dialog. For example, for the tree described with the head vector
0 1 2 3 4 5 6 1 8 9 10 11 12
we can calculate D without arrangement giving
But we can also calculate it with the arrangement
6 5 4 3 2 1 0 7 8 9 10 11 12
which gives
We can also calculate the number of edge crossings. Two edges cross if their positions interleave, i.e., two edges e_1={s,t} and e_2={u,v} cross iff (assuming w.l.o.g. that \pi(s) < \pi(t) and \pi(u) < \pi(v)),
\pi(s) < \pi(u) < \pi(t) < \pi(v) or \pi(u) < \pi(s) < \pi(v) < \pi(t)
For example, the input
gives the following output (the arrangements have been reorganized a bit)
